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;
const int inf = 0x3f3f3f3f, mod = 1e9 + 7;
const int N = 1e7 + 10;
int tot;
int f[N];
int prime[N];
int vis[N];
void Euler() {
  vis[1] = 1;
  for (int i = 2; i < N; ++i) {
    if (vis[i] == 0) prime[++tot] = i;
    for (int j = 1; j <= tot && i * prime[j] < N; ++j) {
      vis[i * prime[j]] = 1;
      if (i % prime[j] == 0) break;
    }
  }
}
long long qpow(long long a, long long b) {
  long long res = 1;
  while (b) {
    if (b & 1) res *= a;
    a *= a;
    b >>= 1;
  }
  return res;
}
long long cal(long long a, long long b) {
  return (1 - qpow(a, b + 1)) / (1 - a);
}
inline void init() {
  Euler();
  f[1] = 1;
  for (int i = 2; i <= 1e7; ++i) {
    long long x = i, y = 1;
    for (int j = 1; j <= tot && x > 1; ++j) {
      int c = 0;
      while (x % prime[j] == 0) {
        x /= prime[j];
        ++c;
      }
      if (c) y *= cal(prime[j], c);
      if (!vis[x]) y *= cal(x, 1), x = 1;
      if (y > 1e7) break;
    }
    if (y > 1e7) break;
    if (f[y] == -1) f[y] = i;
  }
  for (int i = 1; i <= tot; ++i)
    if (f[prime[i] + 1] == -1) f[prime[i] + 1] = min(f[prime[i] + 1], prime[i]);
}
int main(void) {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  int _;
  cin >> _;
  memset(f, -1, sizeof(f));
  init();
  while (_--) {
    int c;
    cin >> c;
    cout << f[c] << '\n';
  }
  return 0;
}
