问题 D: 吉吉的难题

内存限制：512 MB 时间限制：4.000 S

评测方式：文本比较命题人：

提交：3 解决：1

吉吉给聪明的你出了一题:

给定 $N, M$ ，求 $1 \leq x \leq N$ ， $1 \leq y \leq M$ 且 $g cd (x, y)$ 为质数的 $(x, y)$ 有多少对。

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

接下来 $T$ 行，每行两个正整数， $N, M$ 。 $(T \leq 10000$ ， $N, M \leq 10^7)$

T

行，每行一个整数表示第

i

组数据的结果.

2
10 10
100 100

30
2791