popcount 之和

题目描述

求 $1$ 到 $N$ 之间的整数中,除以 $M$ 的余数为 $R$ 的所有整数的 popcount 之和。

这里,正整数 $X$ 的 popcount 是指 $X$ 的二进制表示中 $1$ 的个数,即满足「$X$ 的 $2^k$ 位是 1」的非负整数 $k$ 的个数。

对每个输入,处理 $T$ 组测试数据。

输入格式

输入按以下格式从标准输入给出。第一行如下:

$T$

接下来是 $T$ 组测试数据。每组测试数据的格式如下:

$N$ $M$ $R$

输出格式

输出 $T$ 行。第 $i$ 行输出第 $i$ 组测试数据的答案。

样例

2
12 5 1
6 1 0

6
9

在第 $1$ 组测试数据中,$1$ 的 popcount 是 $1$,$6$ 的 popcount 是 $2$,$11$ 的 popcount 是 $3$,因此应输出 $1+2+3=6$。

在第 $2$ 组测试数据中,$1$ 的 popcount 是 $1$,$2$ 的是 $1$,$3$ 的是 $2$,$4$ 的是 $1$,$5$ 的是 $2$,$6$ 的是 $2$,因此应输出 $1+1+2+1+2+2=9$。

数据范围

• $1 \le T \le 10^5$
• $1 \le M \le N \le 10^9$
• $0 \le R \lt M$
• 输入中的所有值均为整数。