P2257 YY's GCD

After studying number theory, YY gave kAc a problem. Given $N, M$, find the number of pairs $(x, y)$ such that $1 \leq x \leq N$, $1 \leq y \leq M$, and $\gcd(x, y)$ is a prime.

The first line contains an integer $T$ denoting the number of test cases. Then follow $T$ lines, each containing two positive integers $N, M$.

Output $T$ lines, each containing one integer, the answer for the $i$-th test case.

$T = 10^4$, $N, M \leq 10^7$. Translated by ChatGPT 5