UOJ Logo Sharp Sword 剑锋 OI

SSOI

#38. GCD为质数

统计

【问题描述】

求有多少对(x,y)满足gcd(x,y)为质数。(1≤x≤n,1≤y≤m)

【输入格式】

第一行一个正整数T,表示测试数据组数。
接下来T行,每行两正整数n和m。

【输出格式】

输出T行,每组测试数据输出一行表示计算结果

【输入样例1】

3
3 4
10 20
100 300

【输出样例1】

3
56
8319

【时空限制】

15S
256MB

【数据范围】

n,m<=10^7,数据组数不超过10000