记 $\text{popcount}(n)$ 为 $n$ 的二进制表示中 $1$ 的个数。

现在有 $T$ 组询问，每组询问给定 $n, m, r$，请求出

即小于等于 $n$ 且模 $m$ 为 $r$ 的正整数的 $\text{popcount}$ 之和。

$1\le T \le 10^5,\ 1\le m \le n \le 10^9,\ 0\le r < m$。