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

This is the easy 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 $$$\mathbf{x \neq y}$$$ and $$$x \oplus y$$$ is a divisor$$$^{\text{∗}}$$$ of 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 = 6$$$, there are $$$3$$$ valid values for $$$y$$$ among the integers from $$$1$$$ to $$$m = 9$$$, and they are $$$4$$$, $$$5$$$, and $$$7$$$.

- $$$y = 4$$$ is valid because $$$x \oplus y = 6 \oplus 4 = 2$$$ and $$$2$$$ is a divisor of both $$$x = 6$$$ and $$$y = 4$$$.
- $$$y = 5$$$ is valid because $$$x \oplus y = 6 \oplus 5 = 3$$$ and $$$3$$$ is a divisor of $$$x = 6$$$.
- $$$y = 7$$$ is valid because $$$x \oplus y = 6 \oplus 7 = 1$$$ and $$$1$$$ is a divisor of both $$$x = 6$$$ and $$$y = 7$$$.

In the second test case, for $$$x = 5$$$, there are $$$2$$$ valid values for $$$y$$$ among the integers from $$$1$$$ to $$$m = 7$$$, and they are $$$4$$$ and $$$6$$$.

- $$$y = 4$$$ is valid because $$$x \oplus y = 5 \oplus 4 = 1$$$ and $$$1$$$ is a divisor of both $$$x = 5$$$ and $$$y = 4$$$.
- $$$y = 6$$$ is valid because $$$x \oplus y = 5 \oplus 6 = 3$$$ and $$$3$$$ is a divisor of $$$y = 6$$$.

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

Example output:
3
2
1
1
0

Editorial:
THOUGHT: Here $$$x > 0$$$ and $$$y > 0$$$. So $$$x \oplus y$$$ is neither equal to $$$x$$$ nor $$$y$$$. So $$$x \oplus y$$$ is a divisor of $$$x$$$ or $$$y$$$ and $$$x \oplus y < x$$$ or $$$x \oplus y < y$$$.
OBSERVATION: Any divisor $$$d$$$ of $$$p$$$ such that $$$d < p$$$ we know that $$$d \le \lfloor \frac{p}{2} \rfloor$$$.
Also, the highest bits of $$$d$$$ and $$$p$$$ are different when $$$d \le \lfloor \frac{p}{2} \rfloor$$$.
THOUGHT: Wait but $$$x \oplus y$$$ has the same highest bit as $$$y$$$ if $$$y \ge 2 \cdot x$$$.
CONCLUSION: So if $$$y \ge 2 \cdot x$$$, then $$$x \oplus y$$$ can not be a divisor of $$$y$$$.
THOUGHT: But can it be a divisor of $$$x$$$?
OBSERVATION: If $$$y \ge 2 \cdot x$$$, then $$$x \oplus y > x$$$ because the highest bit in $$$x \oplus y$$$ is greater than that in $$$x$$$. So $$$x \oplus y$$$ can not be a divisor of $$$x$$$.
CONCLUSION: If $$$y \ge 2 \cdot x$$$, then $$$x \oplus y$$$ can not be a divisor of $$$x$$$ or $$$y$$$. So no solution in this case.
THOUGHT: Now we need to consider the case when $$$y < 2 \cdot x$$$. But $$$x$$$ is small in this problem, making it feasible to iterate over all possible values of $$$y$$$.
ACTION: Iterate over all possible values of $$$y < 2 \cdot x$$$ and check if $$$x \oplus y$$$ is a divisor of either $$$x$$$ or $$$y$$$.
Time Complexity: $$$\mathcal{O}(x)$$$.