NAJPWG - Playing with GCD

no tags 

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
3
4

 

Case 1: 2
Case 2: 4

 


hide comments
mahilewets: 2017-09-08 14:38:53

Sudden AC after realizing I can precalc for all possible queries

mahilewets: 2017-09-07 16:31:10

I think answer(3)=2 because gcd(2,2)=2>1 and gcd(3,3)=3>1

So there are two pairs

azam_9: 2016-06-22 20:03:31

Beware of output format..costed me many W.A..

Piyush Kumar: 2016-06-21 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.

Ans: Read the statement carefully. You got the point.

Last edit: 2016-12-04 07:26:23
atuldo: 2016-06-19 13:57:25

for N= 3 there are no pairs where gcd is greater than 1

Siddharth Singh: 2016-06-18 09:52:07

Practising On HackerEarth Surely Helped <3
Almost Similar Question There. :)

Rashi Gehani: 2015-05-31 23:18:02

My 100th :-)

Վահագն: 2015-04-20 14:52:49

Last edit: 2015-04-20 15:07:15
Gaurav sharma: 2015-02-19 14:54:04

use long long.......int cost me 1 WA :(


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