RATIONAL - Rational Number

no tags 

Given a number N, find the number of positive irreducible rational numbers less than 1 such that when expressed as P/Q, both P, Q are less than or equal to N.

Input

The first line contain a single integer T, the number of test cases. Following T (<= 1000) lines will contain a test case, a single number N (<= 1000000).

Output

For each test case print the output on a single line.

Example

Input:
3
1
2
3
Output: 0
1
3

hide comments
Anil Kishore: 2009-11-28 13:12:14

given N, we have to find number of irreducible rational numbers of the form P/Q ( < 1 ) and P,Q<=N. For N = 3 (ans=3)--> 1/2 , 1/3 , 2/3. For N = 4 (ans=5)--> 1/2 , 1/3 , 2/3 , 1/4 , 3/4

D3V D PR(): 2009-11-25 14:39:26

explain the question a bit more (with a example )


Added by:Hemant Verma
Date:2009-11-22
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 NODEJS OBJC PERL6 SQLITE VB.NET
Resource:Codechef Snackdown 2009