这是问题的简单版本。两个版本之间的差异以粗体突出显示。只有解决了两个版本的问题后,您才能进行黑客攻击。
Shohag 有两个整数 $$$x$$$ 和 $$$m$$$。帮助他计算整数 $$$1 \le y \le m$$$ 的数量,使得 $$$\mathbf{x \neq y}$$$ 和 $$$x \oplus y$$$ 是 $$$x$$$ 和/或 $$$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 6 9 5 7 2 3 6 4 4 1
输出 #1
3 2 1 1 0
注意
在第一个测试用例中,对于 $$$x = 6$$$,从 $$$1$$$ 到 $$$m = 9$$$ 的整数中有 $$$3$$$ 的 $$$3$$$ 有效值,它们是 $$$4$$$、$$$5$$$ 和 $$$7$$$。
- $$$y = 4$$$ 有效,因为 $$$x \oplus y = 6 \oplus 4 = 2$$$ 和 $$$2$$$ 是 $$$x = 6$$$ 和 $$$y = 4$$$ 的除数。
- $$$y = 5$$$ 有效,因为 $$$x \oplus y = 6 \oplus 5 = 3$$$ 且 $$$3$$$ 是 $$$x = 6$$$ 的除数。
- $$$y = 7$$$ 有效,因为 $$$x \oplus y = 6 \oplus 7 = 1$$$ 和 $$$1$$$ 是 $$$x = 6$$$ 和 $$$y = 7$$$ 的除数。
在第二个测试用例中,对于$$$x = 5$$$,从$$$1$$$到$$$m = 7$$$的整数中有$$$2$$$有效值$$$y$$$,它们是$$$4$$$和$$$6$$$。
- $$$y = 4$$$ 有效,因为 $$$x \oplus y = 5 \oplus 4 = 1$$$ 和 $$$1$$$ 是 $$$x = 5$$$ 和 $$$y = 4$$$ 的除数。
- $$$y = 6$$$ 有效,因为 $$$x \oplus y = 5 \oplus 6 = 3$$$ 且 $$$3$$$ 是 $$$y = 6$$$ 的除数。