Absolute Math

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.

Sample Input

3
6 3
6 2
1 4

Sample Output

12
8
7

Source

2020 Multi-University Training Contest 9