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$)
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$)
For each testcase, output a line, the answer mod 1000000007