## TGCD2 - Trending GCD (Hard)

no tags

This problem is a harder version of TRENDGCD.

Given $n$ and $m$, compute

$$S(n, m) = \sum_{i=1}^n \sum_{j=1}^m ij \cdot f(\gcd(i,j)),$$

where $f(n) = (\mu(n))^2 n$ and $\mu(n)$ is the Möbius function, that is, $f(n) = n$ if $n$ is square-free and $0$ otherwise. Especially, $f(1)=1$.

### 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 $S(n, m)$ modulo $10^9+7$ in a single line.

### Example

Input:
542 1835 120 25123456789 987654321233333333333 233333333333

Output:
306395630128819897063534355737203

### 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 20.76s (total time). (approx 3.46s per file)

WARNING: The time limit may be somewhat strict.

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