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.
//Author: Patel Rag
//Java version "1.8.0_211"
import java.util.*;
import java.io.*;

public class Main
{
  static Reader fr;
  static Print log;
  static class Reader
  {
    private byte[] buffer = new byte[1024];
    private int index;
    private InputStream in;
    private int total;
    public Reader()
    {
        in = System.in;
    }
    public Reader(InputStream in)
    {
      this.in = in;
    }
    private int scan() throws IOException
    {
        if(index >= total)
        {
            index = 0;
            total = in.read(buffer);
            if(total <= 0)
            {
              return -1;
            }
        }
        return buffer[index++];
    }
    public final int nextInt() throws IOException
    {
      return (int)nextLong();
    }
    public final long nextLong() throws IOException
    {
        long res = 0;
        int n = scan();
        while(isWhiteSpace(n))
        {
          n = scan();
        }
        int neg = 1;
        if(n == '-')
        {
            neg = -1;
            n = scan();
        }
        while(!isWhiteSpace(n))
        {
            if(n >= '0' && n <= '9')
            {
                res *= 10;
                res += (n - '0');
                n = scan();
            }
            else
            {
              throw new InputMismatchException();
            }
        }
        return neg*res;
    }
    public final double nextDouble() throws IOException
    {
        double doub = 0;
        int n = scan();
        while(isWhiteSpace(n))
        {
          n=scan();
        }
        int neg = 1;
        if(n == '-')
        {
            neg = -1;
            n = scan();
        }
        while(!isWhiteSpace(n) && n != '.')
        {
            if(n >= '0' && n <= '9')
            {
                doub *= 10;
                doub += n-'0';
                n = scan();
            }
            else
            {
              throw new InputMismatchException();
            }
        }
        if(n == '.')
        {
            n = scan();
            double temp = 1;
            while(!isWhiteSpace(n))
            {
                if(n >= '0' && n <= '9')
                {
                    temp/=10;
                    doub += (n-'0')*temp;
                    n = scan();
                }
                else
                {
                  throw new InputMismatchException();
                }
            }
        }
        return neg*doub;
    }
    public final String next() throws IOException
    {
        StringBuilder sb = new StringBuilder();
        int n = scan();
        while(isWhiteSpace(n))
        {
          n = scan();
        }
        while(!isWhiteSpace(n))
        {
            sb.append((char)n);
            n = scan();
        }
        return sb.toString();
    }
    public final String nextLine() throws IOException
    {
      StringBuilder sb = new StringBuilder();
      int n = scan();
      while(isWhiteSpace(n))
      {
        n = scan();
      }
      while(n != '\n' && n != '\r' && n != -1)
      {
        sb.append((char)n);
        n = scan();
      }
      return sb.toString();
    }
    private boolean isWhiteSpace(int n)
    {
        if(n == ' ' || n == '\n'|| n == '\r' || n == '\t'|| n == -1)
        return true;
        return false;
    }
  }
  static class Print
  {
      private final BufferedWriter bw;
      public Print()
      {
          this.bw = new BufferedWriter(new OutputStreamWriter(System.out));
      }
      public void print(Object object)throws IOException
      {
          bw.append(""+object);
      }
      public void println(Object object)throws IOException
      {
          print(object);
          bw.append("\n");
      }
      public void close()throws IOException
      {
          bw.close();
      }
  }
  public static void main(String[] args)
  throws IOException
  {
    fr = new Reader();
    log = new Print();
    int T = fr.nextInt();
    for(int t = 0; t < T; t++) {
      int n = fr.nextInt();
      if(n % 2 == 0) {
        log.println(n/2 + " " + n/2);
        continue;
      }
      boolean[] comp = new boolean[(int)Math.sqrt(n) + 1];
      boolean done = false;
      for(int i = 2; i <= (int)Math.sqrt(n); i++) {
        if(!comp[i]) {
          if(n % i == 0) {
            int k = n/i;
            log.println(k + " " + (int)(n - k));
            done = true;
            break;
          }
          for(int j = 2*i; j <= (int)Math.sqrt(n); j = j + i) {
            comp[j] = true;
          }
        }
      }
      if(!done) log.println(1 + " " + (int)(n - 1));
    }
    log.close();
  }
}
class pair {
  public final long first;
  public final long second;

  public pair(long first, long second) {
    this.first = first;
    this.second = second;
  }
}
