In Omkar's last class of math, he learned about the least common multiple, or LCM. LCM(a, b) is the smallest positive integer x which is divisible by both a and b.

Omkar, having a laudably curious mind, immediately thought of a problem involving the LCM operation: given an integer n, find positive integers a and b such that a + b = n and LCM(a, b) is the minimum value possible.

Can you help Omkar solve his ludicrously challenging math problem?

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1 ≤ t ≤ 10). Description of the test cases follows.

Each test case consists of a single integer n (2 ≤ n ≤ 10^{9}).

Output

For each test case, output two positive integers a and b, such that a + b = n and LCM(a, b) is the minimum possible.

Example

Input


3
4
6
9


Output


2 2
3 3
3 6

Note

For the first test case, the numbers we can choose are 1, 3 or 2, 2. LCM(1, 3) = 3 and LCM(2, 2) = 2, so we output 2 \ 2.

For the second test case, the numbers we can choose are 1, 5, 2, 4, or 3, 3. LCM(1, 5) = 5, LCM(2, 4) = 4, and LCM(3, 3) = 3, so we output 3 \ 3.

For the third test case, LCM(3, 6) = 6. It can be shown that there are no other pairs of numbers which sum to 9 that have a lower LCM.

import java.util.*;
import java.io.*;
 
 
 public class gfg  {
 
    static PrintWriter out = new PrintWriter(System.out);
    
    public static void main(String[] args) throws IOException{
        //Reader.init(System.in);
        
        Reader.init(System.in);
        int t = Reader.nextInt();
        while(t-->0){
           solve();
        }
        out.close();
    }
    
    static ArrayList<Integer>[] graph; 
    static long n=8;
    static int m=8;
    static int k =0;
    static long mod =1000000007;
    static int MOD = 1000000007;
    static int[] dx = {0,0,1,-1};
    static int[] dy = {1,-1,0,0};
    static int[] cost;
    static int[] col; //0 ,1,2
    static int[] par;
    static long ans=0;
    static ArrayList<Integer> list;

    
    static void solve()throws IOException{
        n = Reader.nextLong();
        long x = printDivisors(n);
        if(n==1){
            out.println(0+" "+1);
            return;
        }
        if(x==-1){
            out.println(1+" "+(n-1));
            return;
        }
        else{
            out.println(n/x+" "+((x-1)*(n))/x) ;
        }
    }
    
    static long printDivisors(long n) 
    { 
        // Note that this loop runs till square root 
        for (int i=2; i<=Math.sqrt(n); i++) 
        { 
            if (n%i==0) 
            { 
                return i;
            } 
        } 
        return -1;
    } 
    
    // ggratest common divisor println
    static int gcd(int a , int b){
        if(b==0)
            return a;
        else
            return gcd(b,a%b);
    }
 
    // least common multiple
    static int lcm(int a, int b){
        return (a*b)/gcd(a,b);
    }
    
    // a^b
    static long fastpow(long a, long b){
        long res = 1;a=a%mod;
        while(b>0){
            if(b%2==1)
                res = (res*a)%mod;
            a = (a*a)%mod;
            b = b>>1;
        }
        return res;
    }

    // segment tree
   /* static void update(int ind, int l, int h, int pos, int v){
        if(l==h){
            seg[ind] = v;
            return;
        }
        int mid = (l+h)/2;
        if(pos<=mid)
            update(2*ind,l,mid,pos,v);
        else
            update(2*ind+1,mid+1,h,pos,v);
        seg[ind] = seg[2*ind]^seg[2*ind+1];
    }
    static int query(int ind, int l , int h, int ll , int hh){
        if(ll>hh)
            return 0;
        if(l==ll && h==hh)
            return seg[ind];
        int mid = (l+h)/2;
        return query(2*ind,l,mid,ll,Math.min(mid,hh)) ^ query(2*ind+1,mid+1,h,Math.max(mid+1,ll),hh);
    }*/
    // priority queue with comparator
    // PriorityQueue<Interval> pq = new PriorityQueue<>(new Comparator<Interval>() {
    //             public int compare(Interval a, Interval b){
    //                 int diff1 = a.r - a.l;
    //                 int diff2 = b.r - b.l;
 
    //                 if(diff1 == diff2){
    //                     return a.l - b.l;
    //                 }
 
    //                 return diff2 - diff1;
    //             }
    // });
}
 
class trienode{
        int v;
        trienode[] child ;
        boolean leaf;
        int cnt;
        int p=0;
        trienode(int vv){
            child = new trienode[2];
            leaf=false;
            cnt=0;
            v=vv;
        }
        trienode(){
            child = new trienode[2];
            leaf=false;
            cnt=0;
            v=0;
        }
    }
class Reader {
    static BufferedReader reader;
    static StringTokenizer tokenizer;
 
    /** call this method to initialize reader for InputStream */
    static void init(InputStream input) {
        reader = new BufferedReader(
                     new InputStreamReader(input) );
        tokenizer = new StringTokenizer("");
    }
 
    /** get next word */
    static String next() throws IOException {
        while ( ! tokenizer.hasMoreTokens() ) {
            //TODO add check for eof if necessary
            tokenizer = new StringTokenizer(
                   reader.readLine() );
        }
        return tokenizer.nextToken();
    }
 
    static int nextInt() throws IOException {
        return Integer.parseInt( next() );
    }
    static long nextLong() throws IOException {
        return Long.parseLong( next() );
    }
    
    static double nextDouble() throws IOException {
        return Double.parseDouble( next() );
    }
}
class newcomparator implements Comparator<Integer>{
    //@Override
    public int compare(Integer a, Integer  b){
        return a<=b?1:-1;
    }
 }
class node {
    int f;
    int s;// cost to rreach\
    node(int ff,int ss){
        f=ff;
        s=ss;
    }
}
class mergesort{
    static void sort(int l, int h, int[] arr){
        if(l<h){
            int mid = (l+h)/2;
            
            sort(l,mid,arr);
            sort(mid+1,h,arr);
            merge(l,mid,h,arr);
        }
    }
    static void merge(int l, int m , int h , int [] arr){

        int[] left = new int[m-l+1];
        int[] right = new int[h-m];
        for(int i= 0 ;i< m-l+1;i++){
            left[i] = arr[l+i];
        }
        for(int i=0;i<h-m;i++){
            right[i] = arr[m+1+i];
        }
        //now left and right arrays are assumed to be sorted and we have tp merge them together 
        // int the original aaray.
        int i=l;
        int lindex = 0;
        int rindex =  0;
        
        while(lindex<m-l+1 && rindex<h-m){
            if(left[lindex]<=right[rindex]){
                arr[i]=left[lindex];
                lindex++;
                i++;
            }
            else{
                arr[i]=right[rindex];
                rindex++;
                i++;
            }
        }
        while(lindex<m-l+1){
            arr[i]=left[lindex];
            lindex++;
            i++;
        }
        while(rindex<h-m){
            arr[i]=right[rindex];
            rindex++;
            i++;
        }
    }
    
}
 
 
