You are given a pseudocode that determines the value of the following function \(f(p,q,n)\):

def f(p,q,n):
    ans=0
    for (i from 1 to n)                          // for loop1
        for (all primes m between p and q )      // for loop2(both p and q inclusive)
            for  (j from 1 to (n/i) )            // for loop3((n/i) does integer division)
                for  (all divisors d of (m*j) )  // for loop4
                    val = ftemp(d)/d             // Not a integer division
                    if(j is odd)
                    ans = ans - val*m*j
                    else
                    ans = ans + val*m*j
    return ans

def ftemp(d): 
    if(d==1)
       return 1
    temp = 0
    for (all prime factors p of d)
        if( d%(p*p) ==0 ) return 0;
        temp = temp+1
    if (temp is even) 
        return 1
    return -1

It can take a large amount of time to write and execute such a lengthy code. Your task is to determine the value of function \(f(p,q,n)\). The value must be modulo \(1000000007\).

Input format

First line: \(t\) denoting the number of test cases
Next \(t\) lines: Three space-separated integers \(p\), \(q\), and \(n\)

Output format

For each test case, print a single line containing answer.\(f(p,q,n) \mod (10^9+7)\).

Constraints

\(1 \le t \le 10 \)

\(2< p<q<10^5\)

\(1 \le n \le 10^9\)