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-10-28 07:09:31 azizul hakim
solved it using loop and gcd. but how to solve it using just if else, no loop? many people seems to solve like that. :/
2015-09-23 18:10:39 Abishek
easy problem! my 50th :) !
2015-09-23 11:25:42 Prakhar Dev Gupta
No use of GCD calculation . Simple if else problem
2015-09-15 18:38:59 Liquid_Science
gives wrong answer instead of a tle -_-
2015-08-25 23:43:07
easy...
just used if...else.......no loop
2015-08-25 06:26:35 Narendra pal
simple and easy...
AC in 1 go ;)
used O(n) ....
2015-08-20 23:01:43 Shivam Singh
Brute Force Algo O(N/2*N/2) gives TLE
Finding GCD using Euclid's Algo works in time O(N/2*log(N/2))
2015-08-19 21:47:06
Accepted in 1 go... :) my 50th one....
2015-08-19 16:45:18
NZEC for java
2015-08-13 08:02:10 Ravi Chandra
Same Like ENIGMATH problem..
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.