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.
#include <bits/stdc++.h>
using namespace std;
int binarySearch(vector<long long> &arr, int left, int right, long long int x,
                 bool is_left = false) {
  if (!is_left) {
    while (left < right) {
      int mid = (left + right) / 2;
      if (x < arr[mid])
        right = mid;
      else
        left = mid + 1;
    }
    return left;
  } else {
    while (left < right) {
      int mid = (left + right) / 2;
      if (x <= arr[mid])
        right = mid;
      else
        left = mid + 1;
    }
    return left;
  }
}
long long int gcd(long long int a, long long int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
int modInverse(int a, int m) {
  a = a % m;
  for (int x = 1; x < m; x++)
    if ((a * x) % m == 1) return x;
}
string reverseStr(string str) {
  string result = str;
  int n = str.length();
  for (int i = 0; i < n / 2; i++) swap(result[i], result[n - i - 1]);
  return result;
}
int parent[1000001];
int depth[1000001];
void make_set(int v) {
  parent[v] = v;
  depth[v] = 0;
}
int find_set(int v) {
  if (v == parent[v]) return v;
  return parent[v] = find_set(parent[v]);
}
void union_sets(int a, int b) {
  a = find_set(a);
  b = find_set(b);
  if (a != b) {
    if (depth[a] < depth[b]) swap(a, b);
    parent[b] = a;
    if (depth[a] == depth[b]) ++depth[a];
  }
}
int tree[32];
void build(vector<long long int> a, int v, int left, int right) {
  if (left == right)
    tree[v] = a[left];
  else {
    int tm = (left + right) / 2;
    build(a, v * 2, left, tm);
    build(a, v * 2 + 1, tm + 1, right);
    tree[v] = max(tree[v * 2], tree[v * 2 + 1]);
  }
}
int get_max(int v, int left, int right, int l, int r) {
  if (l > r) return 0;
  if (l == left && r == right) {
    return tree[v];
  }
  int tm = (left + right) / 2;
  return max(get_max(v * 2, left, tm, l, min(r, tm)),
             get_max(v * 2 + 1, tm + 1, right, max(l, tm + 1), r));
}
void update(int v, int left, int right, int pos, int new_val) {
  if (left == right)
    tree[v] = new_val;
  else {
    int tm = (left + right) / 2;
    if (pos <= tm)
      update(v * 2, left, tm, pos, new_val);
    else
      update(v * 2 + 1, tm + 1, right, pos, new_val);
    tree[v] = max(tree[v * 2], tree[v * 2 + 1]);
  }
}
void bfs(vector<int> g[], bool used[]) {
  queue<int> queue;
  queue.push(1);
  used[1] = true;
  while (!queue.empty()) {
    int u = queue.front();
    queue.pop();
    for (size_t i = 0; i < g[u].size(); ++i) {
      int u = g[u][i];
      if (!used[u]) {
        used[u] = true;
        queue.push(u);
      }
    }
  }
}
int binpow(int a, int n) {
  int res = 1;
  while (n) {
    if (n & 1) res *= a;
    a *= a;
    n >>= 1;
  }
  return res;
}
void reverse(int arr[], int n) {
  for (int i = 0; i < n / 2; i++) swap(arr[i], arr[n - 1 - i]);
}
vector<int> cifar(long long int n) {
  vector<int> ans;
  while (n) {
    ans.push_back(n % 10);
    n = n / 10;
  }
  for (int i = 0; i < ans.size() / 2; i++)
    swap(ans[i], ans[ans.size() - 1 - i]);
  return ans;
}
long long mulmod(long long a, long long b, long long mod) {
  long long res = 0;
  a %= mod;
  while (b) {
    if (b & 1) res = (res + a) % mod;
    a = (2 * a) % mod;
    b >>= 1;
  }
  return res;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  long long int x;
  for (int i = 0; i < n; i++) {
    cin >> x;
    cout << 1 << ' ' << x - 1 << endl;
  }
}
