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$