当前没有测试数据。

Ex - Popcount Sum

得分 : $600$ 分

问题描述

计算所有介于 $1$ 和 $N$ 之间（包括 $N$），并且除以 $M$ 的余数等于 $R$ 的整数的 popcount 之和。
这里，正整数 $X$ 的 popcount 是在 $X$ 的二进制表示中 $1$ 的个数，也就是非负整数 $k$ 的个数，满足 $2^k$ 这个位置是 $1$。
对于每个输入，处理 $T$ 个测试用例。

约束

• $1 \leq T \leq 10^5$
• $1 \leq M \leq N \leq 10^9$
• $0 \leq R < M$
• 输入中的所有值都是整数。

---

输入

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

$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$ 的 popcount 是 $1$，$3$ 的 popcount 是 $2$，$4$ 的 popcount 是 $1$，$5$ 的 popcount 是 $2$，$6$ 的 popcount 是 $2$，所以应该打印 $1+1+2+1+2+2=9$。