Description

There are many unsolvable problem in the world.It could be about one or about zero.But this time it is about bigger number. 

Given an integer n(2 <= n <= 10 

⁹).We should find a pair of 

positive integer a, b so that a + b = n and [a, b] is as large as possible. [a, b] denote the least common multiplier of a, b.

 

Input

The first line contains integer T(1<= T<= 10000),denote the number of the test cases. 

For each test cases,the first line contains an integer n.

 

Output

For each test cases, 

print the maximum [a,b] in a line.

 

Sample Input

3 2 3 4

 

Sample Output

1 2 3

 

#include 
       
        using namespace std;int gcd(int a,int b){    int c=b%a;    while(c>0){        b=a;        a=c;        c=b%a;    }return a;}int main(){    int t;cin>>t;int n;    while(t--){        __int64 sum=0,i;        cin>>n;        for(i=n/2;i>0;i--){            if(gcd(i,n-i)==1)            {                sum=i*(n-i);                break;            }        }        cout<
        
         <