我独自行走,走向远方,穿过渐暗的光芒,等待日落最后的光芒。
— 顺, 查卡
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\cdot10^5$$$。
输出
对于每个测试用例,输出一个整数 - 满足条件的有序元组 $$$(i,j,k)$$$ 的数量。
示例
输入复制
53 24 61 17 20720 2025
输出复制
18254655587864357450
注意
在第一个测试用例中,有 $$$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$$$。