Problem Description

Little White learned the greatest common divisor, so she plan to solve a problem: given x, n，
query ∑gcd(${x}^{a}-1$,${x}^{b}-1$) ($1\leq a,b\leq n$)

Input

The first line of input is an integer T ( $1\leq T\leq 300 $)
For each test case ，the single line contains two integers x and n ( $1\leq x, n \leq 1000000$)

Output

For each testcase, output a line, the answer mod 1000000007

5
3 1
4 2
8 7
10 5
10 8

2
24
2398375
111465
111134466