# Description

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.

3

6 6

8 8

2 20

### Sample Output

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 ø(n)using the formula

```#include<iostream>
#include<cstdio>
using namespace std;
typedef unsigned long long ll;
const int maxx=5001000;
ll a[maxx];
void init()
{
for(int i=0; i<maxx; i++)
a[i]=i;
for(int i=2; i<maxx; i++)
{
if(a[i]==i)
{
for(int j=i; j<maxx; j+=i)
a[j]=a[j]/i*(i-1);
}
}
for(int i=2; i<maxx; i++)
a[i]=a[i]*a[i]+a[i-1];
}
int main()
{
init();
int t,Case=0;
cin>>t;
while(t--)
{
int n,m;
cin>>n>>m;
printf("Case %d: ",++Case);
cout<<a[m]-a[n-1]<<endl;
}
return 0;
}```

## Lightoj 1007 - Mathematically Hard

1007 - Mathematically Hard    PDF (English) Statistics Forum Time Limit: 2 second(s) Memory Limit: 64 MB Mathematically some problems look hard. But with the help of the computer, some problems can be easily solvable. In this problem, you will be giv

## 1007 - Mathematically Hard

PDF (English) Statistics Forum Time Limit: 2 second(s) Memory Limit: 64 MB 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. Yo

## COGS 696. [IOI1996][USACO 2.3] 最长前缀

★   输入文件:prefix.in   输出文件:prefix.out   简单对比时间限制:1 s   内存限制:128 MB 描述 USACO 2.3.1 IOI96 在生物学中,一些生物的结构是用包含其要素的大写字母序列来表示的.生物学家对于把长的序列分解成较短的序列(即元素)很感兴趣. 如果一个集合 P 中的元素可以通过串联(元素可以重复使用,相当于 Pascal 中的 “+” 运算符)组成一个序列 S ,那么我们认为序列 S 可以分解为 P 中的元素.元素不一定要全部出现(如下例中B

## 【BZOJ-1218】激光炸弹 前缀和 + 枚举

1218: [HNOI2003]激光炸弹 Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 1778  Solved: 833[Submit][Status][Discuss] Description 一种新型的激光炸弹,可以摧毁一个边长为R的正方形内的所有的目标.现在地图上有n(N<=10000)个目标,用整数Xi,Yi(其值在[0,5000])表示目标在地图上的位置,每个目标都有一个价值.激光炸弹的投放是通过卫星定位的,但其有一个缺点,就是其爆破