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