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