CF2205G.Simons and Diophantus Equation

I walk alone, into distance, through the fading light, biding my time for the sunset's final light.

— SHUN, CHAKA

Simons has given you two integers $n$ and $m$.

Count the number of ordered tuples $(i, j, k)$, such that:

• $0\le i, j, k\le m$, and
• There exist two integers $x$ and $y$, such that $(i \oplus j) \cdot x + (j \oplus k) \cdot y = n$, where $\oplus$ denotes the bitwise XOR operation.

我独自前行，走向远方，在渐暗的光中徘徊，静候日落的最后一缕光芒。

——SHUN，《CHAKA》（Spotify 链接）

西蒙斯给了你两个整数 $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$ 表示按位异或运算。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The only line contains two integers $n$ and $m$ ($1\le n\le 10^9$, $1\le m\le 3\cdot 10^5$) — the given integers.

It is guaranteed that the sum of $m$ over all test cases does not exceed $3\cdot10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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\cdot10^5$。

For each test case, output a single integer — the number of ordered tuples $(i,j,k)$ that satisfy the condition.

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

In the first test case, there are $18$ tuples that satisfy the conditions. For example:

• $(2,1,2)$ is a valid tuple because the equation $(2\oplus 1)\cdot x+(1\oplus 2)\cdot y=3$ has an integer solution $x=3$, $y=-2$.
• $(1,1,0)$ is also a valid tuple because the equation $(1\oplus 1)\cdot x+(1\oplus 0)\cdot y=3$ has an integer solution $x=100$, $y=3$.
• $(2,0,2)$ is not a valid tuple because the equation $(2\oplus 0)\cdot x+(0\oplus 2)\cdot y=3$ has no integer solution.
• $(1,1,1)$ is not a valid tuple because the equation $(1\oplus 1)\cdot x+(1\oplus 1)\cdot y=3$ has no integer solution.
• $(3,2,1)$ is not a valid tuple because $3 \gt 2$.

在第一个测试用例中，共有 $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 \gt 2$。