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) = n^2 \ , n < x \ and \ gcd(n,x) = 1 $$
To illustrate, 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, 5}. So, score (6) = 22 = 4. For 16, the relatively prime numbers with 16 are {1, 3, 5, 7, 9, 11, 13, 15}. So, score (16) = 82 = 64.
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
Sample Input | Sample Output |
---|---|
3 6 6 8 8 2 20 | Case 1: 4 Case 2: 16 Case 3: 1237 |
Notes
Two integers are said to be relatively prime, if the greatest common divisor for them is 1.
Euler's totient function $\phi(n)$ 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. $\phi(n)$ is read "phi of n."
Given the general prime factorization of $n = p_1^{e1} p_2^{e2} \dots p_m^{em}$, one can compute $\phi(n)$ using the formula:
$$\phi(n) = n \left(1 - \frac{1}{p_1}\right) \left(1 - \frac{1}{p_2}\right) \dots \left(1 - \frac{1}{p_m}\right)$$