Solve the programming task below in a Python markdown code block.
Ma5termind is going through the Euler's book of knowledge when he finds the following function: 

def function(L,R):
    sum=0
    for i in range(L,R+1):              #[L,R]
        for j in range(1,i+1):          #[1,i]
            cnt=0
            if (j)*(j+1) == 2*i :
                for k in range(1,i+1):  #[1,i]
                    if __gcd(k,i)==1:   #__gcd Greatest Common Divisor 
                        cnt+=1
            sum=sum+cnt
    return sum

The function seems weird as well as interesting. Don't you think ?? 

Fascinated by the function, Ma5termind codes it and successfully compiles it in the first go itself. After all, he is a good coder. Ma5termind checks the output computed by the function for all the values of $\mathbf{L}$ and $\mathbf{R}$ in the range $\mathbf{[1,100]}$ and finds that the results are correct.

But as we all know, Ma5termind loves large numbers - very large numbers. When he inputs $\mathbf{L=1}$ & $\mathbf{R=10^{12}}$, the code does not produce any output #TimeLimitExceeded. He still wants to know the answer for such large ranges. Can you help him by writing a code that can also produce an answer for such large ranges?   

Input Format 

First line of input contains a single integer $\mathbf{T}$ denoting the number of test cases. First and the only line of each test case contains two space separated integers $\mathbf{L}$ and $\mathbf{R}$ denoting inputs to the above function.  

Output Format 

Output consists of $\mathbf{T}$ lines each containing result computed by the function when corresponding range is inputted to the function.

Constraints 

$\mathbf{1\leq T\leq10^5}$ 

$\mathbf{1\leq L\leq R\leq10^{12}}$

Sample Input  

2
1 10
2 5

Sample Output  

9
2

Explanation 

Pass Parameters to the function and check the result.