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

bayulaxana: 2017-12-29 08:48:30

You don't need any of GCD, floor, or anything.
The loop is only for the test case (no loops needed)
this is if else problem

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"

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

simple just think for even and odd numbers


Added by:praveen123
Date:2013-08-05
Time limit:0.186s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:IITK ACA CSE online judge