J. Prefix GCD
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

For an array $$$a$$$ of length $$$n$$$, we define the function $$$f(a)$$$ as following: $$$$$${f(a) = gcd(a_1, \space a_1) + gcd(a_1, \space a_2) + ..gcd(a_1, \space a_2, \space ..a_n)}$$$$$$ You are given two positive integers $$$n$$$ and $$$m$$$. You need to output the sum of $$$f(a)$$$ over all arrays $$$a$$$ satisfying the following:

  • The length of the array $$$a$$$ is equal to $$$n$$$.
  • $$${1 \le a_i \le m}$$$ for each $$${1 \le i \le n}$$$.

For two positive integers $$$x$$$ and $$$y$$$, $$$gcd(x, \space y)$$$ equals the greatest integer that divides both $$$x$$$ and $$$y$$$.

Input

The first line contains a single positive integer number $$$t$$$ $$${(1 \le t \le 10^3)}$$$ — the number of testcases.

The first line of each testcase contains two positive integers $$$n$$$ and $$$m$$$ $$${(1 \le n, \space m \le 10^6)}$$$.

Output

For each testcase, output in a separate line the answer described in the statement. Since the output number can be too large, output it modulo $$${10^9 + 7}$$$.

Example
Input
2
1 5
2 9
Output
15
550