DA-IICT Intra Programming Contest 07

Shubhanshu was given a number x and y. He found out the algorithm to find the number of relative prime of a number.Relative prime number of number x is the number from 1 to x-1 , which is relative prime to x.
Pseudocode:
relative_prime(a):
    i=1
    ans=0
    while(i<a):
        if(gcd(i,a)==1):
            ans+=1
        i+=1

return ans

The function gcd(x,y) finds the greatest common divisor of number x and y.
Using this pseudocode he found out the number of relative prime of all number between x and y. But now he get bored and wants you to find the sum of output in the above pseudocode, that is relative_prime(x)+relative_prime(x+1)+.....+relative_prime(y)

Input:
The first line of the input contains test case t. then the next t lines contains x and y.
1<=t<=1000
2<=x,y<=100000

Output:
Output the sum of relative primes from x to y. (x and y included)

Input:
1
3 5

Ouput:
8


Explanation:
In first case ,3 has 2 relative prime number 1 and 2. So 3 has 2 relative prime number. 4 also has two relative prime number that is 1 and 3. Similarly 5 has four relative prime number 1,2,3 and 4.
Therefore You should output the sum of number of relative prime number of 3,4 and 5.
3= 2 relative prime number
4= 2 relative prime number
5= 4 relative prime number
Output: 2+2+4=8.