Let us denote by d(n) the sum of all divisors of the number n, i.e. d(n) = ∑_{k | n} k.

For example, d(1) = 1, d(4) = 1+2+4=7, d(6) = 1+2+3+6=12.

For a given number c, find the minimum n such that d(n) = c.

Input

The first line contains one integer t (1 ≤ t ≤ 10^4). Then t test cases follow.

Each test case is characterized by one integer c (1 ≤ c ≤ 10^7).

Output

For each test case, output: 

  * "-1" if there is no such n that d(n) = c; 
  * n, otherwise. 

Example

Input


12
1
2
3
4
5
6
7
8
9
10
39
691


Output


1
-1
2
3
-1
5
4
7
-1
-1
18
-1
#include <bits/stdc++.h>
using namespace std;
long long binpow(long long first, long long second) {
  long long z = 1;
  while (second > 0) {
    if (second % 2 == 1) z = z * first;
    first = first * first;
    second /= 2;
  }
  return z;
}
int ans[10000009];
int mySize = 2000001;
int arr[2000001];
int getP(int val) {
  for (int i = 2; i * i <= val; i++)
    if (val % i == 0) return i;
  return -1;
}
void solve() {
  for (int i = 0; i < 10000009; i++) ans[i] = -1;
  arr[1] = 1;
  ans[1] = 1;
  for (int i = 2; i < mySize; i++) {
    int p = getP(i);
    if (p == -1) {
      arr[i] = i + 1;
      if (ans[i + 1] == -1) ans[i + 1] = i;
      continue;
    }
    int pw = 1;
    long long num1 = 1;
    long long num2 = i;
    int ok = 1;
    while (num2 % p == 0) {
      num1 += binpow(p, pw);
      if (num1 > 10000009) {
        ok = 0;
        break;
      }
      num2 /= p;
      pw++;
    }
    if (ok == 0) continue;
    arr[i] = arr[num2] * num1;
    if (arr[i] < 10000009 && ans[arr[i]] == -1) ans[arr[i]] = i;
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.precision(17);
  int t;
  cin >> t;
  solve();
  while (t--) {
    int vv;
    cin >> vv;
    if (vv > 1000000 && getP(vv - 1) == -1) {
      cout << vv - 1 << endl;
      continue;
    }
    if (ans[vv] == -1)
      cout << -1 << endl;
    else
      cout << ans[vv] << endl;
  }
  return 0;
}
