CFCF2205G.Simons and Diophantus Equation

我独自前行，走向远方，在渐渐消逝的光中静静等待着日落的最后一缕光。

—— SHUN，CHAKA

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$ 表示按位异或运算。

每组测试数据包含多个测试用例。第一行包含一个整数 $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$。