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

hide comments
ayushgupta1997: 2017-06-18 19:50:59

simple just think for even and odd numbers

sandeep_4141: 2017-06-15 23:07:44

easy one !!
just if-else statement !!
think when n=6 ,10,14,...similar !!

sushanth_r: 2017-04-23 14:29:09

AC in one go with O(1). Simple if else =)

sudeep_11: 2017-01-24 15:41:06

No need to calculate GCD, just find out the pattern !

arindam1234: 2017-01-02 08:29:40

AC in 1 Go!!! My 50th...

mayanksat: 2016-06-09 14:06:08

@ragwave thanks your comment helped ; simple if else implementation.

farhan764: 2016-01-19 21:37:41

python rocks......jus import gcd....

ragwave: 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
Shashank Tiwari: 2015-12-16 10:57:32

Gcd(0,N) = N . So, for N= 1 , Gcd(0,1)=1 .

Pulkit Mittal: 2015-12-06 17:03:56

must use if else


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