问题陈述

给定一个范围在$1$到$N$之间的整数，求所有余数满足除以$M$的余数等于$R$的数的popcount和。
这里，一个正整数$X$的popcount是它的二进制表示中$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$个测试用例的答案。

示例输入1

2
12 5 1
6 1 0

示例输出1

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