Hanumant and His Love
Tag(s):

## Medium-Hard

Problem
Editorial
Analytics

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.

#### Σ(prime<=p) Σ(i=1 to n) Σj=(1 to floor(n/i)) Φ(prime*j)

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.

### Input

First line contains the number of test cases t.

Next t lines contain two space seperated integers p and n.

### Output

For each testcase, print a single line containing the required sum.

### Constraints

1 <= t <= 5
1 <= p <= 10^6
1 <= n <= 10^10

40% score:
p <= 100
n <= 10^4

100% score:
original constraints.

SAMPLE INPUT
2
2 3
3 5
SAMPLE OUTPUT
7
51
Explanation

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.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

CodeBattle

OTHER PROBLEMS OF THIS CHALLENGE
• Math > Number Theory
• Algorithms > Searching