AT_abc283_h [ABC283Ex] Popcount Sum

[problemUrl]: https://atcoder.jp/contests/abc283/tasks/abc283_h $ 1 $ 以上 $ N $ 以下の整数であって、$ M $ で割った余りが $ R $ になるものすべてに対する popcount の総和を求めてください。 ただし、正整数 $ X $ に対して $ X $ の popcount とは $ X $ を二進表記したときの $ 1 $ の個数、すなわち $ 2^k $ の位が $ 1 $ となる非負整数 $ k $ の個数のことです。 $ 1 $ つの入力につき、 $ T $ 個のテストケースに答えてください。

入力は以下の形式で標準入力から与えられる。入力の $ 1 $ 行目は以下の通りである。 > $ T $ そして、$ T $ 個のテストケースが続く。これらはそれぞれ以下の形式で与えられる。 > $ N $ $ M $ $ R $

$ T $ 行出力せよ。$ i $ 行目には $ i $ 番目のテストケースに対する答えを出力せよ。

### 制約 - $ 1\ \leq\ T\ \leq\ 10^5 $ - $ 1\ \leq\ M\ \leq\ N\ \leq\ 10^9 $ - $ 0\ \leq\ R\