← 返回题目列表

Codeforces · 2039/C2

C2. Shohag 喜欢异或(困难版)

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

这是问题的困难版本。两个版本之间的差异以粗体突出显示。只有解决了两个版本的问题后,您才能进行黑客攻击。

Shohag 有两个整数 $$$x$$$ 和 $$$m$$$。帮助他计算 $$$1 \le y \le m$$$ 的整数个数,使得 $$$x \oplus y$$$ 可以被 $$$x$$$ 和/或 $$$x \oplus y$$$ 整除$$$^{\text{*}}$$$。这里 $$$\oplus$$$ 是按位异或运算符。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行也是唯一一行包含两个空格分隔的整数 $$$x$$$ 和 $$$m$$$ ($$$1 \le x \le 10^6$$$, $$$1 \le m \le 10^{18}$$$)。

保证所有测试用例的$$$x$$$总和不超过$$$10^7$$$。

输出

对于每个测试用例,打印一个整数 - 合适的 $$$y$$$ 的数量。

示例

输入 #1

5
7 10
2 3
6 4
1 6
4 1

输出 #1

3
2
2
6
1

注意

在第一个测试用例中,对于 $$$x = 7$$$,从 $$$1$$$ 到 $$$m = 10$$$ 的整数中有 $$$3$$$ 的 $$$y$$$ 有效值,它们是 $$$1$$$、$$$7$$$ 和 $$$9$$$。

- $$$y = 1$$$ 有效,因为 $$$x \oplus y = 7 \oplus 1 = 6$$$ 且 $$$6$$$ 可被 $$$y = 1$$$ 整除。
- $$$y = 7$$$ 有效,因为 $$$x \oplus y = 7 \oplus 7 = 0$$$ 和 $$$0$$$ 可以被 $$$x = 7$$$ 和 $$$y = 7$$$ 整除。
- $$$y = 9$$$ 有效,因为 $$$x \oplus y = 7 \oplus 9 = 14$$$ 且 $$$14$$$ 可被 $$$x = 7$$$ 整除。