题目描述:

定义$GCD(i,j)$为数字$i$,$j$的最大公因数

众所周知,对于一般的$GCD$问题,我们可以轻易的使用某种复杂度为$logn$的算法算出.这种题对于一个身经百炼的ACMer简直是太简单啦.所以显然这道题与一般的$GCD$问题不同

现在你的任务是求出下面式子的值:

因为这个问题的答案可能很大,所以你最终的答案需要对1e9+7取模再输出

输入格式:

本题具有多组输入,第一行一个$T$,表示接下来的输入数据总数

接下来$T$行,每一行输入两个正整数$i,j$,与题目中的对应所述含义相同

输出格式:

输出$T$行,每一行表示对应的$f(i,j)$的值

输入输出样例:

输入#1

3
10 4
3 6
100 45

输出#1

3
7
31

数据范围:

对于$100\%$的测试点保证,$T\in[1,1000],$$i\in[1,1e18],j\in[1,1e18]$