This problem is a harder version of PGCD.

Let $P$ be the set of all prime numbers. For two positive integers $n$ and $m$, define

$f(n,m) = \sum_{i=1}^n \sum_{j=1}^m [\gcd(i,j) \in P],$

which counts the number of prime numbers among the greatest common divisors $\gcd(i,j)$ for $1 \leq i \leq n$ and $1 \leq j \leq m$.

Your task: given $n$ and $m$, compute $f(n,m)$.

Input

The first line contains an integer $T$, indicating the number of test cases.

Each of the next $T$ lines contains two positive integers $n$ and $m$. 

Output

For each test case, print $f(n, m)$ in a single line.

Example

Input:
4
10 10
100 100
123456789 987654321
233333333333 233333333333

Output:
30
2791
33523360713808196
14968599673221238693021

Constraints

There are 6 test files.

Test #0: $1 \leq T \leq 10000$, $1 \leq n, m \leq 10^7$.

Test #1: $1 \leq T \leq 200$, $1 \leq n, m \leq 10^8$.

Test #2: $1 \leq T \leq 40$, $1 \leq n, m \leq 10^9$.

Test #3: $1 \leq T \leq 10$, $1 \leq n, m \leq 10^{10}$.

Test #4: $1 \leq T \leq 2$, $1 \leq n, m \leq 10^{11}$.

Test #5: $T = 1$, $1 \leq n, m \leq 235711131719$.

@Speed Addicts: My solution runs in 4.87s (total time). (approx 0.81s per file)