PGCD2 - Primes in GCD Table (Hard)

no tags

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:
410 10100 100123456789 987654321233333333333 233333333333

Output:
3027913352336071380819614968599673221238693021

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)

 Added by: liouzhou_101 Date: 2019-03-22 Time limit: 20s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All Resource: PGCD