P3957YY的GCD | ||
|
Description
神犇YY虐完数论后给傻×kAc出了一题
给定N, M,求 $1\le x\le N$ , $1\le y\le M$ 且 \(\gcd(x, y)\) 为质数的 \((x, y)\) 有多少对
kAc这种傻×必然不会了,于是向你来请教……
多组输入
Input Format
第一行一个整数 \(T\) 表述数据组数
接下来 \(T\) 行,每行两个正整数,表示 \(N, M\)
Output Format
\(T\) 行,每行一个整数表示第 \(i\) 组数据的结果
Sample Input 1
2
10 10
100 100
Sample Output 1
30
2791
Sample Input 2
5
555 785
450 317
28 26
284 132
602 341
Sample Output 2
120008
39145
207
10277
56504
Hint
$T = 10000 $
\(N, M \le 10190000\)
Source bzoj 2820