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.io.BufferedInputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.PrintWriter;
import java.util.Random;

public class Problem {
	static class Erickde {
		private int BS = 1 << 16;

		private char NC = (char) 0;
		private byte[] buf = new byte[BS];
		private int bId = 0, size = 0;
		private char c = NC;
		private double cnt = 1;
		private BufferedInputStream in;

		public Erickde() {
			in = new BufferedInputStream(System.in, BS);
		}

		public Erickde(String s) {
			try {
				in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
			} catch (Exception e) {
				in = new BufferedInputStream(System.in, BS);
			}
		}

		private char getChar() {
			while (bId == size) {
				try {
					size = in.read(buf);
				} catch (Exception e) {
					return NC;
				}
				if (size == -1)
					return NC;
				bId = 0;
			}
			return (char) buf[bId++];
		}

		public int nextInt() {
			return (int) nextLong();
		}

		public int[] nextInts(int N) {
			int[] res = new int[N];
			for (int i = 0; i < N; i++) {
				res[i] = (int) nextLong();
			}
			return res;
		}

		public long[] nextLongs(int N) {
			long[] res = new long[N];
			for (int i = 0; i < N; i++) {
				res[i] = nextLong();
			}
			return res;
		}

		public long nextLong() {
			cnt = 1;
			boolean neg = false;
			if (c == NC)
				c = getChar();
			for (; (c < '0' || c > '9'); c = getChar()) {
				if (c == '-')
					neg = true;
			}
			long res = 0;
			for (; c >= '0' && c <= '9'; c = getChar()) {
				res = (res << 3) + (res << 1) + c - '0';
				cnt *= 10;
			}
			return neg ? -res : res;
		}

		public double nextDouble() {
			double cur = nextLong();
			return c != '.' ? cur : cur + nextLong() / cnt;
		}

		public String next() {
			StringBuilder res = new StringBuilder();
			while (c <= 32)
				c = getChar();
			while (c > 32) {
				res.append(c);
				c = getChar();
			}
			return res.toString();
		}

		public String nextLine() {
			StringBuilder res = new StringBuilder();
			while (c <= 32)
				c = getChar();
			while (c != '\n') {
				res.append(c);
				c = getChar();
			}
			return res.toString();
		}

		public boolean hasNext() {
			if (c > 32)
				return true;
			while (true) {
				c = getChar();
				if (c == NC)
					return false;
				else if (c > 32)
					return true;
			}
		}
	}

	public static void quicksort(int[] a) {
		if (a == null)
			return;
		quicksort(a, 0, a.length - 1);
	}

	private static void quicksort(int[] a, int lo, int hi) {
		if (lo < hi) {
			int splitPoint = partition(a, lo, hi);
			quicksort(a, lo, splitPoint);
			quicksort(a, splitPoint + 1, hi);
		}
	}

	private static final double EPS = 0.00000001;

	private static int partition(int[] a, int lo, int hi) {
		int pivot = a[lo];
		int i = lo - 1, j = hi + 1;
		while (true) {
			do {
				i++;
			} while (a[i] < pivot);
			do {
				j--;
			} while (a[j] > pivot);
			if (i < j)
				swap(a, i, j);
			else
				return j;
		}
	}

	static int binarySearch(int arr[], int l, int r, int x) {
		if (r >= l) {
			int mid = l + (r - l) / 2;

			if (arr[mid] == x)
				return mid;

			if (arr[mid] > x)
				return binarySearch(arr, l, mid - 1, x);

			return binarySearch(arr, mid + 1, r, x);
		}

		return -1;
	}

	private static void swap(int[] ar, int i, int j) {
		int tmp = ar[i];
		ar[i] = ar[j];
		ar[j] = tmp;
	}

	static Random RANDOM = new Random();

	static int randInt(int min, int max) {
		return RANDOM.nextInt((max - min) + 1) + min;
	}

	public static void main(String[] args) throws Exception {
		Erickde scan = new Erickde();
		PrintWriter out = new PrintWriter(System.out);
		int t = scan.nextInt();
		while (t-- > 0) {
			
			System.out.println("1 " + (scan.nextInt() - 1));

		}
	}

}
