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>
const long long N = 1e7;
const long long mod = 1e9 + 7;
namespace fastIO {
inline void input(long long &res) {
  char c = getchar();
  res = 0;
  long long f = 1;
  while (!isdigit(c)) {
    f ^= c == '-';
    c = getchar();
  }
  while (isdigit(c)) {
    res = (res << 3) + (res << 1) + (c ^ 48);
    c = getchar();
  }
  res = f ? res : -res;
}
inline long long qpow(long long a, long long b) {
  long long ans = 1, base = a;
  while (b) {
    if (b & 1) ans = (ans * base % mod + mod) % mod;
    base = (base * base % mod + mod) % mod;
    b >>= 1;
  }
  return ans;
}
long long fact(long long n) {
  long long res = 1;
  for (long long i = 1; i <= n; i++) {
    res = res * 1ll * i % mod;
  }
  return res;
}
long long C(long long n, long long k) {
  return fact(n) * 1ll * qpow(fact(k), mod - 2) % mod * 1ll *
         qpow(fact(n - k), mod - 2) % mod;
}
}  // namespace fastIO
using namespace fastIO;
using namespace std;
long long n, m;
long long s[N + 100], d[N + 100], ans[N + 100];
vector<long long> primes;
long long mind[N + 100];
signed main() {
  fill(mind, mind + N + 100, -1);
  long long i;
  for (i = 2; i <= N; i++) {
    if (mind[i] == -1) {
      primes.emplace_back(i);
      mind[i] = i;
    }
    for (auto &x : primes) {
      if (x > mind[i] || x * i > N) break;
      mind[x * i] = x;
    }
  }
  s[1] = 1;
  for (long long i = 2; i < N; i++) {
    if (mind[i] == -1) {
      mind[i] = i;
      s[i] = i + 1;
    } else {
      long long j = i;
      s[i] = 1;
      while (j % mind[i] == 0) {
        j /= mind[i];
        s[i] = s[i] * mind[i] + 1;
      }
      s[i] *= s[j];
    }
  }
  fill(ans, ans + N, -1);
  for (long long i = N - 1; i > 0; i--)
    if (s[i] < N) ans[s[i]] = i;
  long long _ = 1;
  input(_);
  while (_--) {
    cin >> n;
    cout << ans[n] << '\n';
  }
  return 0;
}
