Problem Description

Let $f(n)=\sum_{d|n} |\mu(d)|$, where $\mu(d)$ is Mobius function .
Output $\sum_{i=1}^m f(ni)$.

Input

The first line contains an integer $T(1\leq T\leq 10^4)$ - the number of test cases.

Each line of the following $T$ lines contains two integers $n,m (1\leq n,m \leq 10^7)$.

Output

Print the answer modulo $10^9+7$ for each test case.

3
6 3
6 2
1 4

12
8
7