小白学会了求最大公约数，于是打算解决一个问题：给定x,n 求∑gcd(${x}^{a}-1$,${x}^{b}-1$) ($1\leq a,b\leq n$)
第一行输入一个整数T（$1\leq T\leq 300$) 每组数据有一行，有两个整数x和n($1\leq x,n\leq 1000000$)
对于每组数据，输出一行，结果显然很大，对1，000，000，007取模
5 3 1 4 2 8 7 10 5 10 8
2 24 2398375 111465 111134466
