D. Xor And Mul
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given two non-negative integers $$$n$$$ and $$$m$$$, find the number of pairs of integers $$$(x,y)$$$ such that:

  • $$$0 \le x \le n$$$ and $$$0 \le y \le m$$$.
  • $$$(x~\&~y) \cdot (x \oplus y) = x \cdot y$$$.

where $$$\&$$$ represents the bitwise AND operation, and $$$\oplus$$$ represents 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 of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$0 \le n,m \le 10^9$$$).

Output

For each test case, output an integer representing the number of pairs of integers.

Example
Input
5
0 0
1 1
3 7
69 96
114514 191981
Output
1
3
11
166
306496