Mathematically some problems look hard. But with the help of the computer, some problems can be easily solvable.

In this problem, you will be given two integers a and b. You have to find the summation of the scores of the numbers from a to b (inclusive). The score of a number is defined as the following function.

score (x) = n2, where n is the number of relatively prime numbers with x, which are smaller than x

For example,

For 6, the relatively prime numbers with 6 are 1 and 5. So, score (6) = 22 = 4.

For 8, the relatively prime numbers with 8 are 1, 3, 5 and 7. So, score (8) = 42 = 16.

Now you have to solve this task.
Input

Input starts with an integer T (≤ 105), denoting the number of test cases.

Each case will contain two integers a and b (2 ≤ a ≤ b ≤ 5 * 106).
Output

For each case, print the case number and the summation of all the scores from a to b.
Sample Input

Output for Sample Input

3

6 6

8 8

2 20

Case 1: 4

Case 2: 16

Case 3: 1237
Note

Euler’s totient function applied to a positive integer n is defined to be the number of positive integers less than or equal to n that are relatively prime to n. is read “phi of n.”

Given the general prime factorization of , one can compute using the formula

把1-5000000的欧拉函数筛选出来存起来,然后预处理前缀和,注意long long会溢出,要用unsigned long long

/*************************************************************************
    > File Name: LightOJ1007.cpp
    > Author: ALex
    > Mail: zchao1995@gmail.com 
    > Created Time: 2015年06月04日 星期四 17时41分21秒
 ************************************************************************/

#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include