CF2039C2 Shohag Loves XOR (Hard Version)

题为困难版本，简单版本和复杂版本之间的区别以粗体标出。 给定两个整数 $x$ 和 $m$，请找出满足以下条件的整数 $y$ 的个数： - $1⩽y⩽m$。 - $x\oplus y$ 是 $x,y$ 两个数中至少一个数的**倍数**，其中 $\oplus$ 代表异或运算。

输入的第一行包含一个整数 $ t $，表示测试用例的数量，满足 $ 1 \le t \le 10^4 $。 每个测试用例的第一行（也是唯一一行）包含两个用空格分隔的整数 $ x $ 和 $ m $。

对于每个测试用例，输出一个整数，表示符合条件的 $y$ 的数量。

在第一个测试用例中，对于 $ 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 $ 整除。 --- 对于 $100\%$ 的数据，$1⩽t⩽10^4$，$ 1 \le x \le 10^6 $，$ 1 \le m \le 10^{18} $。 保证所有测试用例中 $ x $ 的总和不超过 $ 10^7 $。