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
Output format
For each test case, print a single line containing answer.f(p,q,n)mod(109+7).
Constraints
1≤t≤10
2<p<q<105
1≤n≤109
Substituting the value gives -224