题面翻译

记 $\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$。

样例 #1

样例输入 #1

2
12 5 1
6 1 0

样例输出 #1

6
9

提示

制約

• $1\ \leq\ T\ \leq\ 10^5$
• $1\ \leq\ M\ \leq\ N\ \leq\ 10^9$
• $0\ \leq\ R\ <\ M$