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 static java.lang.Math.abs;
import static java.lang.Math.max;
import static java.lang.Math.min;
import static java.lang.Math.pow;

public class Sol implements Runnable {

  long mod = (long) 1e9 + 7;

  void solve(InputReader in, PrintWriter w) {
    int t = in.nextInt();
    while(t-- > 0) {
      int x = in.nextInt();
      w.println("1 " + (x - 1));
    }
  }

  // ************* Code ends here ***************

  void init() throws Exception {
    //Scanner in;
    InputReader in;
    PrintWriter w;
    boolean online = false;

    String common_in_fileName = "\\input";
    String common_out_fileName = "\\output";
    int test_files = 0;

    for (int file_no = 0; file_no <= test_files; file_no++) {

      String x = "" + file_no;
      if (x.length() == 1) x = "0" + x;

      String in_fileName = common_in_fileName + "" + x;
      String out_fileName = common_out_fileName + "" + x;

      if (online) {
        //in = new Scanner(new File(in_fileName + ".txt"));
        in = new InputReader(new FileInputStream(new File(in_fileName + ".txt")));
        w = new PrintWriter(new FileWriter(out_fileName + ".txt"));
      } else {
        //in = new Scanner(System.in);
        in = new InputReader(System.in);
        w = new PrintWriter(System.out);
      }

      solve(in, w);
      w.close();
    }
  }

  public void run() {
    try {
      init();
    } catch (Exception e) {
      System.out.println(e);
      e.printStackTrace();
    }
  }

  static class InputReader {

    private InputStream stream;
    private BufferedReader br;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;
    private SpaceCharFilter filter;

    public InputReader(InputStream stream) {
      this.stream = stream;
      br = new BufferedReader(new InputStreamReader(stream));
    }

    public int read() {
      if (numChars == -1) {
        throw new InputMismatchException();
      }

      if (curChar >= numChars) {
        curChar = 0;
        try {
          numChars = stream.read(buf);
        } catch (IOException e) {
          throw new InputMismatchException();
        }

        if (numChars <= 0) {
          return -1;
        }
      }
      return buf[curChar++];
    }

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

    public int nextInt() {
      int c = read();

      while (isSpaceChar(c)) {
        c = read();
      }

      int sgn = 1;

      if (c == '-') {
        sgn = -1;
        c = read();
      }

      int res = 0;
      do {
        if (c < '0' || c > '9') {
          throw new InputMismatchException();
        }
        res *= 10;
        res += c - '0';
        c = read();
      } while (!isSpaceChar(c));

      return res * sgn;
    }

    public long nextLong() {
      int c = read();
      while (isSpaceChar(c)) {
        c = read();
      }
      int sgn = 1;
      if (c == '-') {
        sgn = -1;
        c = read();
      }
      long res = 0;

      do {
        if (c < '0' || c > '9') {
          throw new InputMismatchException();
        }
        res *= 10;
        res += c - '0';
        c = read();
      } while (!isSpaceChar(c));
      return res * sgn;
    }

    public double nextDouble() {
      int c = read();
      while (isSpaceChar(c)) {
        c = read();
      }
      int sgn = 1;
      if (c == '-') {
        sgn = -1;
        c = read();
      }
      double res = 0;
      while (!isSpaceChar(c) && c != '.') {
        if (c == 'e' || c == 'E') {
          return res * Math.pow(10, nextInt());
        }
        if (c < '0' || c > '9') {
          throw new InputMismatchException();
        }
        res *= 10;
        res += c - '0';
        c = read();
      }
      if (c == '.') {
        c = read();
        double m = 1;
        while (!isSpaceChar(c)) {
          if (c == 'e' || c == 'E') {
            return res * Math.pow(10, nextInt());
          }
          if (c < '0' || c > '9') {
            throw new InputMismatchException();
          }
          m /= 10;
          res += (c - '0') * m;
          c = read();
        }
      }
      return res * sgn;
    }

    public String readString() {
      int c = read();
      while (isSpaceChar(c)) {
        c = read();
      }
      StringBuilder res = new StringBuilder();
      do {
        res.appendCodePoint(c);
        c = read();
      } while (!isSpaceChar(c));

      return res.toString();
    }

    public boolean isSpaceChar(int c) {
      if (filter != null) {
        return filter.isSpaceChar(c);
      }
      return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    public String next() {
      return readString();
    }

    public interface SpaceCharFilter {

      public boolean isSpaceChar(int ch);
    }
  };

  public static void main(String args[]) throws Exception {
    new Thread(null, new Sol(), "Sol", 1 << 28).start();
  }
}