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
2017-06-18 19:50:59
simple just think for even and odd numbers
2017-06-15 23:07:44
easy one !!
just if-else statement !!
think when n=6 ,10,14,...similar !!
2017-04-23 14:29:09
AC in one go with O(1). Simple if else =)
2017-01-24 15:41:06
No need to calculate GCD, just find out the pattern !
2017-01-02 08:29:40
AC in 1 Go!!! My 50th...
2016-06-09 14:06:08
@ragwave thanks your comment helped ; simple if else implementation.
2016-01-19 21:37:41
python rocks......jus import gcd....
2016-01-01 21:14:02
jst write down numbers from 30 to 40 on a paper,and study the answer pattern.......its jst if/else problem!!
use long long int.!!

Last edit: 2016-01-01 21:14:45
2015-12-16 10:57:32 Shashank Tiwari
Gcd(0,N) = N . So, for N= 1 , Gcd(0,1)=1 .
2015-12-06 17:03:56 Pulkit Mittal
must use if else
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.