题目描述

求

$$\sum_{i=1}^n\sum_{j=1}^m\gcd(i,j)\varphi(ij)\mu(ij)$$

输出结果模 $2^{32}$。

输入格式

本题有多组数据。

第一行是数据组数 $T$。$(1\le T\le 17)$

接下来 $T$ 行，每行两个正整数 $n,m$，为本次询问的参数。$(1\le n,m\le 5\times 10^7$，$\sum \max(n,m) \le 4\times 10^8)$

输出格式

对每组数据，输出一行一个非负整数表示答案模 $2^{32}$ 的值。

样例

样例输入

3
5 5
10 10
233 666

样例输出

15
4294967291
3538331