#3309. DZY Loves Math

内存限制:512 MiB 时间限制:20 Sec

题目描述

对于正整数n,定义f(n)为n所含质因子的最大幂指数。例如f(1960)=f(2^3 * 5^1 * 7^2)=3, f(10007)=1, f(1)=0。
给定正整数a,b,求sigma(sigma(f(gcd(i,j)))) (i=1..a, j=1..b)。

输入格式

第一行一个数T,表示询问数。
接下来T行,每行两个数a,b,表示一个询问。

输出格式

对于每一个询问,输出一行一个非负整数作为回答。

样例

样例输入


			
4
7558588 9653114
6514903 4451211
7425644 1189442
6335198 4957

样例输出


			
35793453939901
14225956593420
4332838845846
15400094813

数据范围与提示

【数据规模】

T<=10000

1<=a,b<=10^7