C2. Shohag 爱异或（困难版）

时间限制：每个测试点 $2$ 秒
内存限制：$256$ 兆字节

这是该问题的困难版。两个版本之间的差异已用粗体标出。只有当你解决了两个版本的问题时，才能进行 $hack$。

$Shohag$ 有两个整数 $x$ 和 $m$。请帮助他统计满足 $1 \le y \le m$ 且 $x \oplus y$ 能被 $x$ 或 $y$（或同时两者）整除的整数 $y$ 的个数。这里 $\oplus$ 表示按位异或运算符。

若存在整数 $c$ 使得 $a = b \cdot c$，则称数 $a$ 能被数 $b$ 整除。

输入
第一行包含一个整数 $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$ 的数量。

示例
输入：

5
7 10
2 3
6 4
1 6
4 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$ 整除。