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 <= 10^12;

Output

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

Example

Input:
4
3
4
5
100

Output:
1
1
2
49

hide comments
awas_mohan2021: 2023-05-02 21:18:06

think brutforce better

lokesh_2052: 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
davidgalehouse: 2019-02-01 04:59:02

Don't worry about n==1 case.

anurag_018: 2018-12-25 15:30:24

ac in one go

satyamlal2209: 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.

ameyanator: 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 :)

karthik_vg: 2018-01-04 14:51:29

brute force it and get the pattern and then its O(1)

sanyam19: 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

the_phoenixx: 2017-06-28 15:13:24

develop the pattern and thats it

rohit9934: 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"


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