## 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:
4345100 Output:
11249```

## Code Examples

### #1 Code Example with Python Programming

```Code - Python Programming```

``````def gcd(a, b):
while a > 0 and b > 0:
if a >= b:
a %= b
else:
b %= a
return a + b
T = int(input())
for _ in range(T):
N = int(input())
for i in range(N // 2, 0, -1):
if gcd(N, i) == 1:
print(i)
break``````
Copy The Code &

Input

cmd
4
3
4
5
100

Output

cmd
1
1
2
49

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````#include<bits/stdc++.h>
using namespace std;
#define pi 3.14159265358979323846264338327950
const int N=1e6+20,mod=(int)(1e9)+7;
#define ONLINE_JUDEGE
#define pb push_back
#define ull unsigned long long
#define ll long long
int main(){
#ifdef ONLINE_JUDEGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int T;
scanf("%d",&T);
while(T--){
ll num;
cin>>num;
ll ans=(ll)floor(num/2);
if(num%2)
cout<<ans-1<<endl;
else
cout<<ans<<endl;
}
return(0);
} ``````
Copy The Code &

Input

cmd
4
3
4
5
100

Output

cmd
1
1
2
49