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组数据的结果。