← 返回题目列表

Codeforces · 2205/G

G. 西蒙斯和丢番图方程

中文机器翻译题面 查看原题

我独自行走,走向远方,穿过渐暗的光芒,等待日落最后的光芒。
— 顺, 查卡

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)$$$ 的数量。

示例

输入
复制

5
3 2
4 6
1 1
7 20
720 2025

输出
复制

18
254
6
5558
7864357450

注意

在第一个测试用例中,有 $$$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$$$。