PGCD - Primes in GCD Table

给定 $N,M$，求 $1\leq x \leq N, 1\leq y\leq M$ 且 $\gcd(x, y)$ 为质数的 $(x, y)$ 有多少对。 第一行一个整数 $T$，表述数据组数。 接下来 $T$ 行，每行两个正整数，表示 $N, M$。 $1\le N,M\le10^7$，$T\le 10$。

Johnny has created a table which encodes the results of some operation -- a function of two arguments. But instead of a boring multiplication table of the sort you learn by heart at prep-school, he has created a GCD (greatest common divisor) table! So he now has a table (of height a and width b), indexed from (1,1) to (a,b), and with the value of field (i,j) equal to gcd(i,j). He wants to know how many times he has used prime numbers when writing the table.

First, t

For each test case write one number - the number of prime numbers Johnny wrote in that test case.

2
10 10
100 100

30
2791