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 realy 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 
Output 
2

Case 1: 2 
hide comments
thiefthief:
20191005 07:10:46
??????? Last edit: 20191005 07:40:34 

selfcoder24:
20190713 17:29:24
Concept of Phi and observation. Be extra sure on the output format :) 

immim:
20181222 06:03:14
Phi Sieve + Cumulative sum.....See output format. :) 

m2do:
20180312 19:36:09
Euler Totient + DP <3 

itachi_2016:
20180102 15:27:33
Very easy ! 

chetan4060:
20180101 11:45:39
ac in second go:)


mahilewets:
20170908 14:38:53
Sudden AC after realizing I can precalc for all possible queries 

mahilewets:
20170907 16:31:10
I think answer(3)=2 because gcd(2,2)=2>1 and gcd(3,3)=3>1


azam_9:
20160622 20:03:31
Beware of output format..costed me many W.A.. 

Piyush Kumar:
20160621 16:53:55
@atuldo, It is not mentioned that x and y cannot be equal. So for N=3, (2,2) and (3,3) are pairs whose gcd is greater than 1.

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