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;
void err(istream_iterator<string> it) {}
template <typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
  cerr << *it << " = " << a << endl;
  err(++it, args...);
}
template <typename T_vector>
void output_vector(const T_vector &v, bool add_one = false, int start = -1,
                   int end = -1) {
  if (start < 0) start = 0;
  if (end < 0) end = int(v.size());
  for (int i = start; i < end; i++)
    cout << v[i] + (add_one ? 1 : 0) << (i < end - 1 ? ' ' : '\n');
}
long long int mul(long long int a, long long int b, long long int m) {
  return (((a % m) * (b % m)) % m);
}
long long int power(long long int x, long long int y);
bool ispower2(long long int n) { return n && (!(n & (n - 1))); }
long long int seive[1000 + 10];
void solve() {
  long long int c;
  cin >> c;
  if (c == 1) {
    cout << "1\n";
    return;
  }
  for (int i = 2; i <= c; i++) {
    unordered_map<long long int, long long int> mp;
    long long int n = i;
    while (n != 1) {
      if (seive[n] == 1) {
        mp[n]++;
        break;
      }
      mp[seive[n]]++;
      n /= seive[n];
    }
    long long int sum = 1;
    for (auto x : mp) {
      sum *=
          (((long long int)power(x.first, x.second + 1) - 1) / (x.first - 1));
    }
    if (sum == c) {
      cout << i << "\n";
    }
  }
  cout << "-1\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long int n = 1000 + 5;
  for (int i = 0; i < n; i++) seive[i] = 1;
  for (long long int i = 2; i * i <= n; i++) {
    if (seive[i] == 1) {
      for (long long int j = i * i; j <= n; j += i) {
        seive[j] = i;
      }
    }
  }
  long long int t = 1, z = 1;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}
long long int power(long long int x, long long int y) {
  long long int res = 1;
  while (y > 0) {
    if (y & 1) res = res * x;
    y = y >> 1;
    x = x * x;
  }
  return res;
}
