Home Web Board ProblemSet Standing Status Statistics
long long输出请使用 %lld服务器的python版本为3.4
Problem D: 三队-杭州-简易数论

Problem D: 三队-杭州-简易数论

Time Limit: 15 Sec  Memory Limit: 128 MB
Submit: 57  Solved: 30
[Submit][Status][Web Board]

Description

计算

       ∑f(i)(1 <= i <= n)

       f(i) 为[ i , i^2 ]中与i互质的数的个数(a,b互质即gcd(a,b)=1)

       由于结果很大,请对结果取模1e9+7

Input


第一行为整数T,代表T组数据

每组数据的第一行一个整数N

       限制:

       1 <= T <= 50

       1 <= N <= 10^6

Output

对每组数据输出一行'Case #x: y',代表第x组数据答案为y

Sample Input

3
1
10
100

Sample Output

Case #1: 1
Case #2: 186
Case #3: 200042

HINT

[Submit][Status][Web Board]