CF2205G Simons and Diophantus Equation

我独自前行，走向远方，在渐渐消逝的光中静静等待着日落的最后一缕光。 —— SHUN，[CHAKA](https://open.spotify.com/track/1WL7sDRLAWmMGGJgQMUAGv) Simons 给了你两个整数 $n$ 和 $m$。 请你计算有多少个有序三元组 $(i, j, k)$ 满足以下条件： - $0\le i, j, k\le m$，并且 - 存在整数 $x$ 和 $y$，使得 $(i \oplus j) \cdot x + (j \oplus k) \cdot y = n$，其中 $\oplus$ 表示[按位异或运算](https://en.wikipedia.org/wiki/Bitwise_operation#XOR)。

每组测试数据包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例数量。 接下来每组测试用例包含一行，包含两个整数 $n$ 和 $m$（$1\le n\le 10^9$，$1\le m\le 3\cdot 10^5$）——给定的整数。 保证所有测试用例中 $m$ 的总和不超过 $3\cdot 10^5$。

对于每个测试用例，输出一个整数，表示满足条件的有序三元组 $(i,j,k)$ 的数量。

在第一个测试用例中，共有 $18$ 个满足条件的三元组。例如： - $(2,1,2)$ 是一个合法的三元组，因为方程 $(2\oplus 1)\cdot x+(1\oplus 2)\cdot y=3$ 存在整数解 $x=3$，$y=-2$。 - $(1,1,0)$ 也是一个合法的三元组，因为方程 $(1\oplus 1)\cdot x+(1\oplus 0)\cdot y=3$ 存在整数解 $x=100$，$y=3$。 - $(2,0,2)$ 不是合法的三元组，因为方程 $(2\oplus 0)\cdot x+(0\oplus 2)\cdot y=3$ 没有整数解。 - $(1,1,1)$ 不是合法的三元组，因为方程 $(1\oplus 1)\cdot x+(1\oplus 1)\cdot y=3$ 没有整数解。 - $(3,2,1)$ 不是合法的三元组，因为 $3 > 2$。 由 ChatGPT 5 翻译