{"problem":{"name":"Ex - Popcount Sum","description":{"content":"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 i","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc283_h"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nThe 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc283_h","tags":[],"sample_group":[["2\n12 5 1\n6 1 0","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."]],"created_at":"2026-03-03 11:01:13"}}