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