IITKWPCB - Check the coprimeness

Find largest non-negative number less than or equal to floor (N/2) which is coprime to N.

Two number a and b are considered to coprime if gcd(a, b) = 1.

Input

T : number of test  cases (T ≤ 1000).

For next T lines, every line contains n (1 ≤ n ≤ 1012).

Output

For each test case, output the answer as described in the problem statement.

Example

Input:
4
3
4
5
100

Output:
1
1
2
49

Added by:praveen123
Date:2013-08-05
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:IITK ACA CSE online judge

hide comments
2015-08-11 18:41:34 shantanu tripathi
remember it will be 0 for n=1.... caused me one wrng ans :(
2015-07-16 17:52:36
use long long int and if n==1 o/p is 0 and it's better if you start the loop running from (n/2) to 1 rather than from 1 to (n/2) to avoid tle :D ac 0.0ss
2015-07-10 09:41:53 SangKuan
esay
2015-06-12 15:52:44 ATUL GUPTA
use scanf and printf instead cin and cout otherwise you get TLE
2015-06-08 19:34:02 Rishabh Agarwal
use long long int for c
2015-04-21 21:47:03 ANUJ RATHORE
its so easy....
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.