Problem Description

DZY loves math since he was very young. One day he meets this problem:

Calculate $\sum_{1\le i\le n} \sum_{1\le j \le m} \gcd(i \text{ AND } j, i \text{ OR } j)$。$\gcd(a,b)$ means the greatest common divisor of $a,b$. When $a\neq 0$, define $\gcd(0,a)=a$。AND, OR means bitwise and, or operation.

DZY says he has been tired of such kind of problems, so he leaves it to you.

Input

First line contains $t$, meaning there are $t$ testcases.

$t$ testcases follow. Each testcase has a line containing two integers $n,m$.

($1\le t \le 3,1\le n,m \le 15000$. There are at most $2$ testcases such that $\max\{n,m\}>2000$. There are at most $1$ testcase such that $\max\{n,m\}>8000$)

Output

Output the answer in one line for each testcase.

3
3 5
30 50
210 15000

43
15467
2660805398