You are given a positive integer x. Find any such 2 positive integers a and b such that GCD(a,b)+LCM(a,b)=x.

As a reminder, GCD(a,b) is the greatest integer that divides both a and b. Similarly, LCM(a,b) is the smallest integer such that both a and b divide it.

It's guaranteed that the solution always exists. If there are several such pairs (a, b), you can output any of them.

Input

The first line contains a single integer t (1 ≤ t ≤ 100) — the number of testcases.

Each testcase consists of one line containing a single integer, x (2 ≤ x ≤ 10^9).

Output

For each testcase, output a pair of positive integers a and b (1 ≤ a, b ≤ 10^9) such that GCD(a,b)+LCM(a,b)=x. It's guaranteed that the solution always exists. If there are several such pairs (a, b), you can output any of them.

Example

Input


2
2
14


Output


1 1
6 4

Note

In the first testcase of the sample, GCD(1,1)+LCM(1,1)=1+1=2.

In the second testcase of the sample, GCD(6,4)+LCM(6,4)=2+12=14.
import java.util.*;
import java.io.*;
import java.math.*;
// Journey Planning
public class Main {
    static void solve(Scanner sc, PrintWriter pw) throws IOException {
        int t = sc.nextInt();
        while (t-->0) {
            long x = sc.nextLong(), d = 1, gcd = 1, nx = x;
            // for (long i = 2; i < x; i++) {
            //     if (0 == x % i) {
            //         d = i;
            //         break;
            //     }
            // }
            if  (x == 3) {
                pw.println(1 + " " +  2);
                continue;
            }
            if (d > 1) {
                while (0 == nx % d) {
                    gcd*= d;
                    nx/= d;
                }
            }
            // pw.println("  " + x + ":");
            long res[] = new long[2];
            factor(x / gcd - 1, res);
            // pw.println("   dd " + gcd);
            long a = res[0] * gcd, b = res[1] * gcd;
            pw.println(a+ " " + b);
            long gg = gcdc(a, b), mm = a/gcd *b;
            // gg = 10; 
            // pw.println(gg + mm == x);
            // assert gg + mm == x :  "error " + x;
            // pw.println(t);
        }
    }
    static void factor(long ab, long res[]) {
        // System.out.println("   factoring " + ab);
        if (ab == 1) {
            res[0] = 1;
            res[1] = 1;
            return;
        }
        if (ab == 2) {
            res[0] = 1;
            res[1] = 2;
        }
        long d = 1, nab = ab;
        for (long i = 2; i <= Math.sqrt(ab); i++) {
            if (checkPrime(i) && 0 == ab % i) {
                d = i;
                break;
            }
        }
        // System.out.println("   factoring dd " + d);
        res[0] = 1;
        if (d > 1) {
            while (0 == ab % d) {
                ab/= d;
                res[0]*= d;
            }
        }
        res[1] = nab / res[0];
    }
    static boolean checkPrime(long n) 
    { 
        BigInteger b = new BigInteger(String.valueOf(n)); 
  
        return b.isProbablePrime(1); 
    } 
    /**
        GCD
    **/
    static long gcdc(long a, long b) {
        if (a > b) {
            long t = a;
            a = b;
            b = t;
        }
        while (a > 0) {
            long t = b % a;
            b = a;
            a = t;
        }
        return b;
    }

    static long TIME_START, TIME_END;
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        PrintWriter pw = new PrintWriter(new BufferedOutputStream(System.out));

        Runtime runtime = Runtime.getRuntime();
        long usedMemoryBefore = runtime.totalMemory() - runtime.freeMemory();
        TIME_START = System.currentTimeMillis();
        solve(sc, pw);
        TIME_END = System.currentTimeMillis();
        long usedMemoryAfter = runtime.totalMemory() - runtime.freeMemory();
        pw.close();
        // System.err.println("Memory increased: " + (usedMemoryAfter - usedMemoryBefore) / 1000000);
        // System.err.println("Time used: " + (TIME_END - TIME_START) + ".");
    }

    // The input scanner
//     static class Scanner {
//         StringTokenizer st;
//         BufferedReader br;

//         public Scanner(InputStream s) {
//             br = new BufferedReader(new InputStreamReader(s));
//         }

//         public Scanner(FileReader s) throws FileNotFoundException {
//             br = new BufferedReader(s);
//         }

//         public String next() throws IOException {
//             while (st == null || !st.hasMoreTokens())
//                 st = new StringTokenizer(br.readLine());
//             return st.nextToken();
//         }

//         public int nextInt() throws IOException {
//             return Integer.parseInt(next());
//         }

//         public long nextLong() throws IOException {
//             return Long.parseLong(next());
//         }

//         public String nextLine() throws IOException {
//             return br.readLine();
//         }

//         public double nextDouble() throws IOException {
//             return Double.parseDouble(next());
//         }

//         public boolean ready() throws IOException {
//             return br.ready();
//         }
    }
// }
