AT_abc283_h.[ABC283Ex] Popcount Sum

请计算所有满足以下条件的整数的 popcount 总和：这些整数在 $1$ 到 $N$ 之间，且除以 $M$ 的余数为 $R$。
其中，对于正整数 $X$，$X$ 的 popcount 指的是 $X$ 的二进制表示中 $1$ 的个数，即所有使得 $2^k$ 位为 $1$ 的非负整数 $k$ 的个数。
对于每组输入，请回答 $T$ 个测试用例。

输入通过标准输入给出。输入的第 $1$ 行如下：

$T$

接下来是 $T$ 个测试用例。每个测试用例格式如下：

$N$ $M$ $R$

请输出 $T$ 行，第 $i$ 行输出第 $i$ 个测试用例的答案。

限制条件

• $1 \leq T \leq 10^5$
• $1 \leq M \leq N \leq 10^9$
• $0 \leq R < M$
• 输入均为整数

样例解释 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$。

由 ChatGPT 4.1 翻译