Home => ProblemSet => YY的GCD
Problem2257--YY的GCD

2257: YY的GCD

Time Limit: 4 Sec  Memory Limit: 512 MB  Submit: 0  Solved: 0
[ Submit ] [ Status ] [ Creator: ][ 参考程序 ]

Description

给定 N,M,求 1≤x≤N,1≤y≤M 且 gcd(x,y) 为质数的 (x,y) 有多少对。

Input

第一行一个整数 T 表述数据组数。
接下来 T 行,每行两个正整数,N,M。

Output

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

Sample Input Copy

2
10 10
100 100

Sample Output Copy

30
2791

HINT

T=104,N,M≤107

Source/Category