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
2023-05-02 21:18:06
think brutforce better
2021-02-26 12:23:06
<snip> Please correct if i'am wrong

[NG]: It's wrong to spoil.

Last edit: 2021-02-26 16:15:15
2019-02-01 04:59:02
Don't worry about n==1 case.
2018-12-25 15:30:24
ac in one go
2018-06-30 17:20:57
Just make sure that if you are using C you might keep getting a wrong answer even though your logic might be correct because of the incorrect data type. Use unsigned long long int and also while using printf, try using inttype.h library! otherwise,core logic is simple.
2018-03-01 20:56:21
Easy Question. At first I just ran a loop to find the GCD=1 condition it passed (had guessed that we'll always have an answer) but then the comments provided with another approach the pattern approach which was too easy to code :)
2018-01-04 14:51:29
brute force it and get the pattern and then its O(1)
2017-11-07 09:38:57
no need of gcd,floor,just should hv an idea of coprime no. i.e. they have only d factor 1 in common
2017-06-28 15:13:24
develop the pattern and thats it
2017-06-26 20:12:45
waste my time where O(1) solution exists. Problem statement should be changed to "See the test cases and develop solution"
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.