Find the sum of popcounts of all integers between $1$ and $N$, inclusive, such that the remainder when divided by $M$ equals $R$.  
Here, the popcount of a positive integer $X$ is the number of $1$s in the binary notation of $X$, that is, the number of non-negative integers $k$ such that the $2^k$s place is $1$.  
For each input, process $T$ test cases.

The input is given from Standard Input in the following format. The first line is as follows:

```
$T$
```

$T$ test cases follow. Each of them is given in the following format:

```
$N$ $M$ $R$
```

Print $T$ lines. The $i$\-th line should contain the answer to the $i$-th test case.

-   $1 \leq T \leq 10^5$
-   $1 \leq M \leq N \leq 10^9$
-   $0 \leq R < M$
-   All values in the input are integers.

6
9

In the 1-st test case, the popcount of 1 is 1, the popcount of 6 is 2, and the popcount of 1111 is 3, so 1+2+3=6 should be printed.
In the 2-nd test case, the popcount of 1 is 1, 2 is 1, 3 is 2, 4 is 1, 5 is 2, and 6 is 2, so 1+1+2+1+2+2=9 should be printed.