承太郎的"替身数"
时间限制：C/C++/Rust/Pascal 4秒，其他语言8秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

空条承太郎是一名海洋学家，不过他最近研究起了数学。他知道每一个大于2的正整数都能写成若干个质数的乘积的形式，即A=p_1^{a_1} p_2^{a_2}p_3^{a_3}……，其中pi都是质数，ai都是正整数。现在有两个数A，B分别可以写成A=p_1^{a_1} p_2^{a_2}p_3^{a_3}……，B=p_1^{b_1} p_2^{b_2}p_3^{b_3}……，一定存在一个C=p_1^{max(a_1,b_1)} p_2^{max(a_2,b_2)}p_3^{max(a_3,b_3)}……，显然A，B都能整除C，承太郎把这个C命名为（A，B）的“替身数”。现在他有两个正整数S1和S2，从1到S1中任意取一个正整数为A，1到S2中任意取一个正整数数为B，就能得到一个“替身数”C，现在他想知道他能得到的所有“替身数“的和为多少，这个答案可能很大，所以他想要答案对1e9+7取模。

输入描述:


第一行输入一个t表示有t组S1，S2(t<=20)
第二行两个数S1，S2(S1，S2<=1e7)

输出描述:

对每组测试输出一个正整数，表示“替身数”的和mod 1e9+7的值
示例1

输入

复制 
1
4 5

输出

复制 
122