G. Simons and Diophantus Equation
time limit per test
6 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

I walk alone, into distance, through the fading light, biding my time for the sunset's final light.
— SHUN, CHAKA

Simons has given you two integers $$$n$$$ and $$$m$$$.

Count the number of ordered tuples $$$(i, j, k)$$$, such that:

  • $$$0\le i, j, k\le m$$$, and
  • There exist two integers $$$x$$$ and $$$y$$$, such that $$$(i \oplus j) \cdot x + (j \oplus k) \cdot y = n$$$, where $$$\oplus$$$ denotes the bitwise XOR operation.
Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The only line contains two integers $$$n$$$ and $$$m$$$ ($$$1\le n\le 10^9$$$, $$$1\le m\le 3\cdot 10^5$$$) — the given integers.

It is guaranteed that the sum of $$$m$$$ over all test cases does not exceed $$$3\cdot10^5$$$.

Output

For each test case, output a single integer — the number of ordered tuples $$$(i,j,k)$$$ that satisfy the condition.

Example
Input
5
3 2
4 6
1 1
7 20
720 2025
Output
18
254
6
5558
7864357450
Note

In the first test case, there are $$$18$$$ tuples that satisfy the conditions. For example:

  • $$$(2,1,2)$$$ is a valid tuple because the equation $$$(2\oplus 1)\cdot x+(1\oplus 2)\cdot y=3$$$ has an integer solution $$$x=3$$$, $$$y=-2$$$.
  • $$$(1,1,0)$$$ is also a valid tuple because the equation $$$(1\oplus 1)\cdot x+(1\oplus 0)\cdot y=3$$$ has an integer solution $$$x=100$$$, $$$y=3$$$.
  • $$$(2,0,2)$$$ is not a valid tuple because the equation $$$(2\oplus 0)\cdot x+(0\oplus 2)\cdot y=3$$$ has no integer solution.
  • $$$(1,1,1)$$$ is not a valid tuple because the equation $$$(1\oplus 1)\cdot x+(1\oplus 1)\cdot y=3$$$ has no integer solution.
  • $$$(3,2,1)$$$ is not a valid tuple because $$$3 \gt 2$$$.