DZY从小就喜欢数学。 有一天他遇到这么一个题：
计算$\sum_{1\le i\le n} \sum_{1\le j \le m} \gcd(i \text{ AND } j, i \text{ OR } j)$。其中$\gcd(a,b)$表示$a,b$的最大公约数，当$a\neq 0$时规定$\gcd(0,a)=a$。AND和OR分别表示按位与、按位或运算。
DZY说这种题他已经做腻了，于是就把它丢给了你。
第一行$t$，表示有$t$组数据。
接下来$t$组数据。每组数据包含一行两个整数$n,m$。
($1\le t \le 3,1\le n,m \le 15000$，至多有$2$组数据使得$\max\{n,m\}>2000$，至多有$1$组数据使得$\max\{n,m\}>8000$)
每组数据输出一行答案。
3 3 5 30 50 210 15000
43 15467 2660805398