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 翻译