YY的GCD

神犇 YY 虐完数论后给傻× kAc 出了一题 给定 $N, M$，求 $1 \leq x \leq N$，$1 \leq y \leq M$ 且 $\gcd(x, y)$ 为质数的 $(x, y)$ 有多少对。

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

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

2
10 10
100 100

30
2791

$T = 10^4$，$N, M \leq 10^7$。