gcd

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 131072/131072 K (Java/Others)

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

Sample Input

5 3 1 4 2 8 7 10 5 10 8

Sample Output

2 24 2398375 111465 111134466

Hint

wange2014

Source

BestCoder Round #85

提交代码