1370A Maximum GCD #div2

A. Maximum GCD

 

Let's consider all integers in the range from 1 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)$\mathrm{g}\mathrm{c}\mathrm{d}(a,b)$, where 1≤a<b≤n$1\le a<b\le n$.

The greatest common divisor, gcd(a,b)$\mathrm{g}\mathrm{c}\mathrm{d}(a,b)$, of two positive integers a$a$ and b$b$ is the biggest integer that is a divisor of both a$a$ and b$b$.

Input

The first line contains a single integer t$t$ (1≤t≤100$1\le t\le 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$n$ (2≤n≤106$2\le n\le {10}^6$).

Output

For each test case, output the maximum value of gcd(a,b)$\mathrm{g}\mathrm{c}\mathrm{d}(a,b)$ among all 1≤a<b≤n$1\le a<b\le n$.

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)=1$\mathrm{g}\mathrm{c}\mathrm{d}(1,2)=\mathrm{g}\mathrm{c}\mathrm{d}(2,3)=\mathrm{g}\mathrm{c}\mathrm{d}(1,3)=1$.

In the second test case, 2$2$ is the maximum possible value, corresponding to gcd(2,4)$\mathrm{g}\mathrm{c}\mathrm{d}(2,4)$.

1. #include<iostream>
2. using namespace std;
3. int main(){
4. int t;cin>>t;
5. while(t--){
6. long n;
7. cin>>n; long a[n];
9. for(int i=1;i<=n;i++)a[i]=i;
10.  
11. cout<<a[n]/2<<endl;
12.  ///or cout<< n/2<<endl;
13.  
14.  
15. }
16.  
17. }