C2. Shohag Loves XOR (Hard Version)time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputThis is the hard version of the problem. The differences between the two versions are highlighted in bold. You can only make hacks if both versions of the problem are solved.Shohag has two integers $$$x$$$ and $$$m$$$. Help him count the number of integers $$$1 \le y \le m$$$ such that $$$x \oplus y$$$ is divisible$$$^{\text{∗}}$$$ by either $$$x$$$, $$$y$$$, or both. Here $$$\oplus$$$ is the bitwise XOR operator.$$$^{\text{∗}}$$$The number $$$a$$$ is divisible by the number $$$b$$$ if there exists an integer $$$c$$$ such that $$$a = b \cdot c$$$.InputThe first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.The first and only line of each test case contains two space-separated integers $$$x$$$ and $$$m$$$ ($$$1 \le x \le 10^6$$$, $$$1 \le m \le 10^{18}$$$).It is guaranteed that the sum of $$$x$$$ over all test cases does not exceed $$$10^7$$$.OutputFor each test case, print a single integer — the number of suitable $$$y$$$.ExampleInput57 102 36 41 64 1Output3
2
2
6
1
NoteIn the first test case, for $$$x = 7$$$, there are $$$3$$$ valid values for $$$y$$$ among the integers from $$$1$$$ to $$$m = 10$$$, and they are $$$1$$$, $$$7$$$, and $$$9$$$. $$$y = 1$$$ is valid because $$$x \oplus y = 7 \oplus 1 = 6$$$ and $$$6$$$ is divisible by $$$y = 1$$$. $$$y = 7$$$ is valid because $$$x \oplus y = 7 \oplus 7 = 0$$$ and $$$0$$$ is divisible by both $$$x = 7$$$ and $$$y = 7$$$. $$$y = 9$$$ is valid because $$$x \oplus y = 7 \oplus 9 = 14$$$ and $$$14$$$ is divisible by $$$x = 7$$$.