Shohag Loves XOR (Hard Version)
Contest: CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
Difficulty rating: 1800
Tags: bitmasks, brute force, math, number theory

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.

Input format:
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 format:
For each test case, print a single integer — the number of suitable $$$y$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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

Example input:
5
7 10
2 3
6 4
1 6
4 1

Example output:
3
2
2
6
1

Editorial:
THOUGHT: Consider the three cases of when $$$x \oplus y$$$ is divisible by $$$x$$$, $$$y$$$, or both separately.
Case 1: $$$x \oplus y$$$ is divisible by $$$x$$$.
THOUGHT: Let $$$p = x \oplus y$$$. So $$$y = p \oplus x$$$. So we can rephrase the problem as counting the number of integers $$$p$$$ such that $$$p$$$ is divisible by $$$x$$$ and $$$1 \le p \oplus x \le m$$$.
OBSERVATION: $$$p \oplus x \le p + x$$$, because xor is just addition without carry.
THOUGHT: So it feels like almost all values of $$$p \le m$$$ might work! And it's actually true because $$$p \oplus x \le p + x \le m$$$, so if $$$p + x \le m$$$ i.e. $$$p \le m - x$$$ then $$$p \oplus x \le m$$$ is always true.
CONCLUSION: All multiples of $$$x$$$ under $$$m - x$$$ always work! So the count is $$$\lfloor \frac{m - x}{x} \rfloor$$$.
THOUGHT: But how about when $$$p > m - x$$$?
OBSERVATION: if $$$p > x$$$, then $$$p \oplus x \ge p - x$$$, because xor is like subtraction without borrowing.
THOUGHT: So if $$$p - x > m$$$ i.e. $$$p > m + x$$$ then $$$p \oplus x \ge p - x > m$$$ is always true.
CONCLUSION: So no values of $$$p$$$ work when $$$p > m + x$$$.
THOUGHT: And there are two multiples of $$$x$$$ in the range $$$(m - x, m + x]$$$. So we can just check them manually.
CONCLUSION: Answer is $$$\lfloor \frac{m - x}{x} \rfloor$$$ plus manually checking the two multiples of $$$x$$$ in the range $$$(m - x, m + x]$$$.
Case 2: $$$x \oplus y$$$ is divisible by $$$y$$$.
THOUGHT: As we already know that $$$x \oplus y \le x + y$$$, and when $$$x < y$$$, $$$x \oplus y \le x + y < y + y = 2 \cdot y$$$.
But as $$$x > 0$$$ and $$$y > 0$$$, so $$$x \oplus y$$$ is neither $$$x$$$ nor $$$y$$$, so the smallest multiple of $$$y$$$ that can work is $$$2 \cdot y$$$. But $$$x \oplus y < 2 \cdot y$$$, so no solution here.
CONCLUSION: No solution when $$$x < y$$$. And as $$$x$$$ is small in this problem, so we can just iterate over all values of $$$y \le x$$$ and manually check if $$$x \oplus y$$$ is divisible by $$$y$$$.
Case 3: $$$x \oplus y$$$ is divisible by both $$$x$$$ and $$$y$$$.
THOUGHT: So the xor is divisible by $$$\text{lcm}(x, y)$$$. So when $$$x \neq y$$$, $$$\text{lcm}(x, y) \ge 2 \cdot \max(x, y)$$$ but $$$x \oplus y < 2 \cdot \max(x, y)$$$, so no solution here.
CONCLUSION: Only works when $$$y = x$$$.
FINAL CONCLUSION: So we just implement the above cases and the answer is the sum of case $$$1$$$ and case $$$2$$$ subtracted by case $$$3$$$.
Time Complexity: $$$\mathcal{O}(x)$$$.