这是问题的困难版本。两个版本之间的差异以粗体突出显示。只有解决了两个版本的问题后,您才能进行黑客攻击。
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$$$ 整除。