题目描述

$1$ 以上 $N$ 以下の整数であって、$M$ で割った余りが $R$ になるものすべてに対する popcount の総和を求めてください。
ただし、正整数 $X$ に対して $X$ の popcount とは $X$ を二進表記したときの $1$ の個数、すなわち $2^k$ の位が $1$ となる非負整数 $k$ の個数のことです。
$1$ つの入力につき、 $T$ 個のテストケースに答えてください。

输入格式

入力は以下の形式で標準入力から与えられる。入力の $1$ 行目は以下の通りである。

$T$

そして、$T$ 個のテストケースが続く。これらはそれぞれ以下の形式で与えられる。

$N$ $M$ $R$

输出格式

$T$ 行出力せよ。$i$ 行目には $i$ 番目のテストケースに対する答えを出力せよ。

题目大意

记 $\text{popcount}(n)$ 为 $n$ 的二进制表示中 $1$ 的个数。

现在有 $T$ 组询问，每组询问给定 $n, m, r$，请求出

即小于等于 $n$ 且模 $m$ 为 $r$ 的正整数的 $\text{popcount}$ 之和。

$1\le T \le 10^5,\ 1\le m \le n \le 10^9,\ 0\le r < m$。

2
12 5 1
6 1 0

6
9

提示

制約

• $1\ \leq\ T\ \leq\ 10^5$
• $1\ \leq\ M\ \leq\ N\ \leq\ 10^9$
• $0\ \leq\ R\ <\ M$
• 入力はすべて整数

Sample Explanation 1

$1$ つ目のテストケースでは、$1$ の popcount が $1$、$6$ の popcount が $2$、$11$ の popcount が $3$ であるため $1+2+3$ の計算結果である $6$ を出力します。 $2$ つ目のテストケースでは、$1$ の popcount が $1$、$2$ の popcount が $1$、$3$ の popcount が $2$、$4$ の popcount が $1$、$5$ の popcount が $2$、$6$ の popcount が $2$ であるため $1+1+2+1+2+2$ の計算結果である $9$ を出力します。