Shivam got upset with Hanumant and Gurwinder due to some misunderstanding between them. Gurwinder being the matured one, comes up with an awesome idea to settle the matter.
Since we know that Hanumant is the best when it comes to mathematics and loves it so much that he cannot remain upset with anyone who comes up with interesting mathematical challenges, so Gurwinder asks Shivam to prepare an interesting mathematical probelm and challenge Hanumant. The challenge is to find the value of the expression below.
Since Shivam himself does not know the solution to the challenge, help him solve it so that he can verify Hanumant's solution.
floor(x) : the greatest integer that is less than or equal to x.
Φ is the Euler Totient Function.
Note: Since the answer can be very large, you need to print answer modulo 10^9+7.
First line contains the number of test cases t.
Next t lines contain two space seperated integers p and n.
For each testcase, print a single line containing the required sum.
1 <= t <= 5
1 <= p <= 10^6
1 <= n <= 10^10
40% score:
p <= 100
n <= 10^4
100% score:
original constraints.
Test case 1 :
The only prime<=2 is 2 itself.
Given Φ(2*1)+Φ(2*2)+Φ(2*3)+Φ(2*1)+Φ(2*1) = (1+2+2+1+1) = 7.