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.io.*;
import java.text.DecimalFormat;
import java.util.*;
/*
        author : Aditya Aggarwal

        LinkedIn : https://www.linkedin.com/in/aditya7861/

        ' The Dawn does not come twice to awaken the man '  ---->>>  ( My Motivation )

        Believe In yourself, Everything is possible.

        Never Give Up ... Failure is the biggest success
 */

public class Main
{

    static class AdityaFastIO
    {
        final private int BUFFER_SIZE = 1 << 16;
        private final DataInputStream din;
        private final byte[] buffer;
        private int bufferPointer, bytesRead;
        BufferedReader br;
        StringTokenizer st;

        public AdityaFastIO()
        {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public AdityaFastIO(String file_name) throws IOException
        {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        String word()
        {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        String line()
        {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }

        public String readLine() throws IOException
        {
            byte[] buf = new byte[64]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1)
            {
                if (c == '\n')
                    break;
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }

        public int ni() throws IOException
        {
            int ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do
            {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');

            if (neg)
                return -ret;
            return ret;
        }

        public long nl() throws IOException
        {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }

        public double nd() throws IOException
        {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();

            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');

            if (c == '.')
            {
                while ((c = read()) >= '0' && c <= '9')
                {
                    ret += (c - '0') / (div *= 10);
                }
            }

            if (neg)
                return -ret;
            return ret;
        }

        private void fillBuffer() throws IOException
        {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }

        private byte read() throws IOException
        {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }

        public void close() throws IOException
        {
            if (din == null)
                return;
            din.close();
        }
    }

    static int MOD = (int) (1e9 + 7);

    static long powerLL(long x, long n)
    {
        long result = 1;
        while (n > 0)
        {
            if (n % 2 == 1)
            {
                result = result * x % MOD;
            }
            n = n / 2;
            x = x * x % MOD;
        }
        return result;
    }

    static long powerStrings(String sa, String sb)
    {
        long a = 0, b = 0;

        for (int i = 0; i < sa.length(); i++)
        {
            a = (a * 10 + (sa.charAt(i) - '0')) %
                    MOD;
        }

        for (int i = 0; i < sb.length(); i++)
        {
            b = (b * 10 + (sb.charAt(i) - '0')) %
                    (MOD - 1);
        }

        return powerLL(a, b);
    }

    static long gcd(long a, long b)
    {
        if (a==0) return b;
        else return gcd(b%a,a);
    }

    static long lcm(long a, long b)
    {
        return (a*b)/gcd(a,b);
    }

    static long lower_bound(List<Long> list, long k)
    {
        int s = 0;
        int e = list.size();

        while (s!=e)
        {
            int mid = (s+e)>>1;

            if (list.get(mid)<k) s = mid+1;
            else e = mid;
        }

        if (s == list.size()) return -1;
        return s;
    }

    static int upper_bound(List<Long> list, long k)
    {
        int s = 0;
        int e = list.size();

        while (s!=e)
        {
            int mid = (s+e)>>1;

            if (list.get(mid)<=k) s = mid+1;
            else e = mid;
        }

        if (s == list.size()) return -1;
        return s;
    }

    static void print(Object o) throws IOException {
        OutputStream out = new BufferedOutputStream(System.out);

        out.write((o+"").getBytes());

        out.flush();
    }

    static void println(Object o) throws IOException {
        OutputStream out = new BufferedOutputStream(System.out);
        out.write((o+"\n").getBytes());
        out.flush();
    }

    static void addEdge(ArrayList<ArrayList<Integer>>graph, int edge1, int edge2)
    {
        graph.get(edge1).add(edge2);
        graph.get(edge2).add(edge1);
    }

    static class Pair<X,Y>
    {
        public X first;
        public Y second;

        Pair(X first, Y second)
        {
            this.first = first;
            this.second = second;
        }

        public static <X,Y> Pair <X,Y> of (X a, Y b)
        {
            return new Pair<>(a,b);
        }

        public String toString()
        {
            return "("+first+","+second+")";
        }
    }

    static boolean isCollectionsSorted(List<Integer> list)
    {
        if (list.size() == 0 || list.size() == 1) return true;

        for (int i=1;i<list.size();i++) if (list.get(i)>list.get(i-1)) return false;

        return true;
    }

    public static void main(String[] args) throws java.lang.Exception
    {
        try
        {
            AdityaFastIO r = new AdityaFastIO();

            try (OutputStream out = new BufferedOutputStream(System.out))
            {

                boolean tc = true;

                int testcases = tc?r.ni():1;

                while (testcases -- > 0)
                {
                    int a = r.ni();

                    int b = 1;

                    int i=2;
                    while (i<=Math.sqrt(a)) {
                        if (a%i == 0)
                        {
                            b = a/i;
                            break;
                        }
                        i++;
                    }

                    println(a-b+" "+b);
                }
            }
        }
        catch(Exception e){}
        finally{}
    }
}


//(()) () (()((()()()())))

 		  	 	 	  	    	  	      			