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;
template <class T>
void pv(T a, T b) {
  for (T i = a; i != b; ++i) cerr << *i << " ";
  cerr << endl;
}
const int maxn = 1e7 + 100;
int fat[maxn], prime[maxn], np;
int func[maxn];
int M[maxn];
int find(int c) {
  if (M[c] > 0) return M[c];
  if (c - 1 > 1 and fat[c - 1] == c - 1) return c - 1;
  return -1;
}
int main() {
  vector<int> slow(100 + 10);
  for (int n = 1; n <= 100; n++) {
    int d = 0;
    for (int i = 1; i <= n; i++) {
      if (n % i == 0) d += i;
    }
    slow[n] = d;
  }
  fat[1] = 1;
  for (int i = 2; i < maxn; i++) {
    if (fat[i] == 0) fat[i] = prime[np++] = i;
    for (int j = 0; j < np; j++) {
      int next = i * prime[j];
      if (next < maxn)
        fat[next] = min(prime[j], fat[i]);
      else
        break;
      if (i % prime[j] == 0) break;
    }
  }
  M[1] = 1;
  func[1] = 1;
  for (int i = 2; i < maxn; i++) {
    if (fat[i] == i) {
      func[i] = i + 1;
    } else {
      int p = fat[i], x = i, m = 1;
      long long s = 0, over = 0;
      while (x % p == 0) {
        s += x;
        x /= p;
        m *= p;
        if (s >= maxn) over = 1;
      }
      if (x == 1) {
        if (over)
          func[i] = -1;
        else
          func[i] = s + 1;
      } else {
        if (func[x] < 0 or func[m] < 0 or func[x] >= maxn / func[m])
          func[i] = -1;
        else
          func[i] = func[x] * func[m];
      }
    }
    if (i <= 100) assert(func[i] == slow[i]);
    if (func[i] > 0) M[func[i]] = i;
  }
  std::ios::sync_with_stdio(false);
  cin.tie(0);
  int T = 1;
  cin >> T;
  for (int t = 0; t < T; t++) {
    int c;
    cin >> c;
    cout << find(c) << "\n";
  }
  cout.flush();
  return 0;
}
