{"raw_statement":[{"iden":"problem statement","content":"Find the sum of popcounts of all integers between $1$ and $N$, inclusive, such that the remainder when divided by $M$ equals $R$.  \nHere, 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$.  \nFor each input, process $T$ test cases."},{"iden":"constraints","content":"*   $1 \\leq T \\leq 10^5$\n*   $1 \\leq M \\leq N \\leq 10^9$\n*   $0 \\leq R < M$\n*   All values in the input are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format. The first line is as follows:\n\n$T$\n\n$T$ test cases follow. Each of them is given in the following format:\n\n$N$ $M$ $R$"},{"iden":"sample input 1","content":"2\n12 5 1\n6 1 0"},{"iden":"sample output 1","content":"6\n9\n\nIn the $1$\\-st test case, the popcount of $1$ is $1$, the popcount of $6$ is $2$, and the popcount of $11$ is $3$, so $1+2+3=6$ should be printed.  \nIn 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."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}