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:
5
42 18
35 1
20 25
123456789 987654321
233333333333 233333333333
Output:
306395
630
128819
897063534
355737203

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.