NAJPWG - Playing with GCD

Tanmoy recently learn about Euclid gcd algorithm. This algorithm looks like:

gcd(a, b):
   if (b == 0): return a
   return gcd(b, a % b)

Now he want to find out how many pair (x, y) can be possible in range N, which gcd is greater than 1. Here pair (x, y) and (y, x) consider as same pair. 1<=x, y<=N.

He can find out it small number easily but for a large number its really hard to find out. Now he needs your help. Write a programme that find out number of such pair.

Input

Input start with an integer number T ( ≤ 10^5), which is number of test cases.

Each test case contain a integer N (1 ≤ N ≤ 10^5).

Output

For each case, print case number and desired answer

Sample

Input:
2
3
4

Output:
Case 1: 2
Case 2: 4

Added by:Najmuzzaman
Date:2014-10-31
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2022-06-11 22:06:04
little bit tricky....

Last edit: 2022-06-11 22:06:37
2022-01-07 09:01:34
observation on phi + prefix sum :)
2020-08-05 08:00:52
About output format : There's no blank line before the first test case. And there's a space between "Case" and the case number, and between the colon (':') and the answer.
2020-07-16 18:16:04
Beware of the output format , There is no next line before the test case 1

About output format Ans: There's no blank line before the first test case. And there's a space between "Case" and the case number, and between the colon (':') and the answer.

Last edit: 2020-12-20 11:18:02
2019-07-13 17:29:24
Concept of Phi and observation. Be extra sure on the output format :-)
2018-12-22 06:03:14
Phi Sieve + Cumulative sum.....See output format. :)
2018-03-12 19:36:09
Euler Totient + DP <3
2018-01-02 15:27:33
Very easy !
2018-01-01 11:45:39
ac in second go:-)
very conceptual question .
2017-09-08 14:38:53
Sudden AC after realizing I can precalc for all possible queries
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.