M. ModulOR Equation
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given two integers $$$n$$$ and $$$m$$$.

Find the number of ordered pairs $$$(a, b)$$$ that satisfy:

  • $$$1 \le a \le n$$$;
  • $$$1 \le b \le m$$$;
  • $$$(a \bmod b)$$$ $$$+$$$ $$$(b \bmod a)$$$ $$$=$$$ $$$(a$$$ $$$|$$$ $$$b)$$$.

Note that $$$|$$$ denotes the bitwise OR operator.

Input

The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of testcases. Description of each testcase follows.

Each testcase contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 10^6 $$$).

It is guaranteed that the sum of $$$n$$$ over all testcases does not exceed $$$10^6$$$ and the sum of $$$m$$$ over all testcases does not exceed $$$10^6$$$.

Output

For each testcase, print the answer on a separate line.

Example
Input
5
6 7
20 20
998 244
353 420
1000 1000
Output
9
62
5475
9338
50200