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.

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

Simons and Diophantus Equation

Examples