505039 - gcd表中的质数

【题目描述】gcd表中的质数(gcdtable)

有一个M×N的表格,行与列分别是1~M和1~N,格子中间写着行与列的最大公约数gcd(i,j)(1≤i≤M, 1≤j≤N)。 例如M = 5,n = 4的表格如表5.4所示。

表5.4

1	2	3	4	5

1 1 1 1 1 1 2 1 2 1 2 1 3 1 1 3 1 1 4 1 2 1 4 1

给出M和N,求这张表中有多少个质数。

输入

第一行一个整数T(1≤T≤1000),表示测试数据组数。 接下来T行,每行两个正整数N和M(N,M≤10^7)。

输出

T行,每行一个整数表示第i组数据的结果。

样例

输入

【输入格式】
2
10 10
100 100

输出

30
2791
时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题