Description

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.

Input Format

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 Format

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

2
10 10
100 100

30
2791

Hint

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

Translated by ChatGPT 5