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 $。