Algorithm

A. Maximum GCD
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Let's consider all integers in the range from 11 to n (inclusive).

Among all pairs of distinct integers in this range, find the maximum possible greatest common divisor of integers in pair. Formally, find the maximum value of gcd(a,b)gcd(�,�), where 1a<bn1≤�<�≤�.

The greatest common divisor, gcd(a,b)gcd(�,�), of two positive integers a and b is the biggest integer that is a divisor of both a and b.

Input

The first line contains a single integer t (1t1001≤�≤100)  — the number of test cases. The description of the test cases follows.

The only line of each test case contains a single integer n (2n1062≤�≤106).

Output

For each test case, output the maximum value of gcd(a,b)gcd(�,�) among all 1a<bn1≤�<�≤�.

Example
input
Copy
2
3
5

output
Copy
1
2

Note

In the first test case, gcd(1,2)=gcd(2,3)=gcd(1,3)=1gcd(1,2)=gcd(2,3)=gcd(1,3)=1.

In the second test case, 22 is the maximum possible value, corresponding to gcd(2,4)gcd(2,4).

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include<bits/stdc++.h>
using namespace std;

int main(){
int t;
cin>>t;
int n;
while(t--){
cin>>n;
if(n%2 != 0){
n--;
cout<<(n/2)<<endl;
continue;
}
cout<<(n/2)<<endl;
}
return 0;
}
Copy The Code &

Input

cmd
2
3
5

Output

cmd
1
2

Demonstration

Codeforcess solution 1370-A A. Maximum GCD ,C++, Java, Js and Python,1370-A,Codeforcess solution