This 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$.

Input

The 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$.

Output

For each test case, print a single integer — the number of suitable $y$.

Note

In 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$.