C1. Shohag Loves XOR (Easy Version)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

$$$^{\text{∗}}$$$The number $$$b$$$ is a divisor of the number $$$a$$$ 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$$$.

Example
Input
5
6 9
5 7
2 3
6 4
4 1
Output
3
2
1
1
0
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$$$.