BZOJ原题地址

洛谷原题地址

题目描述

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

输入输出

输入格式

第一行一个整数T 表述数据组数。

接下来T行,每行两个正整数,表示N, M。

输出格式

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

样例

输入

输出

思路

我们要求的是 $sum_{i=1}^{n}sum_{j=1}^{m}[gcd(x,y)=prime]$。
然后。。。

坑。

代码