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 A>
void read(vector<A> &v);
template <class A, size_t S>
void read(array<A, S> &a);
template <class T>
void read(T &x) {
  cin >> x;
}
void read(double &d) {
  string t;
  read(t);
  d = stod(t);
}
void read(long double &d) {
  string t;
  read(t);
  d = stold(t);
}
template <class H, class... T>
void read(H &h, T &...t) {
  read(h);
  read(t...);
}
template <class A>
void read(vector<A> &x) {
  for (auto &a : x) read(a);
}
template <class A, size_t S>
void read(array<A, S> &x) {
  for (auto &a : x) read(a);
}
string to_string(char c) { return string(1, c); }
string to_string(bool b) { return b ? "true" : "false"; }
string to_string(const char *s) { return string(s); }
string to_string(string s) { return s; }
string to_string(vector<bool> v) {
  string res;
  for (int i = (0); (1) > 0 ? i < ((int)(v).size()) : i > ((int)(v).size());
       i += (1))
    res += char('0' + v[i]);
  return res;
}
template <size_t S>
string to_string(bitset<S> b) {
  string res;
  for (int i = (0); (1) > 0 ? i < (S) : i > (S); i += (1))
    res += char('0' + b[i]);
  return res;
}
template <class T>
string to_string(T v) {
  bool f = 1;
  string res;
  for (auto &x : v) {
    if (!f) res += ' ';
    f = 0;
    res += to_string(x);
  }
  return res;
}
template <class A>
void write(A x) {
  cout << to_string(x);
}
template <class H, class... T>
void write(const H &h, const T &...t) {
  write(h);
  write(t...);
}
void print() { write("\n"); }
template <class H, class... T>
void print(const H &h, const T &...t) {
  write(h);
  if (sizeof...(t)) write(' ');
  print(t...);
}
void DBG() { cerr << "]" << endl; }
template <class H, class... T>
void DBG(H h, T... t) {
  cerr << to_string(h);
  if (sizeof...(t)) cerr << ", ";
  DBG(t...);
}
long long binexp(long long a, long long b) {
  long long ans = 1;
  while (b) {
    if (b & 1) {
      ans = ans * a;
    }
    a *= a;
    b /= 2;
  }
  return ans;
}
long long sumofdiv(long long x) {
  map<long long, long long> m;
  while (x % 2 == 0) {
    x /= 2;
    m[2]++;
  }
  for (long long i = 3; i * i <= x; i += 2) {
    while (x % i == 0) {
      x /= i;
      m[i]++;
    }
  }
  if (x > 1) m[x]++;
  long long ans = 1;
  for (auto x : m) {
    ans *= ((binexp(x.first, x.second + 1) - 1) / (x.first - 1));
  }
  return ans;
}
map<long long, int> sumdiv;
void precompute() {
  sumdiv.clear();
  for (long long i = 2; i <= 1e6; i++) {
    long long ans = sumofdiv(i);
    sumdiv[ans] = i;
  }
}
void solve() {
  int n;
  read(n);
  sumdiv[1] = 1;
  if (sumdiv.count(n)) {
    print(sumdiv[n]);
  } else {
    print(-1);
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int t = 1;
  precompute();
  read(t);
  for (int i = (0); (1) > 0 ? i < (t) : i > (t); i += (1)) {
    solve();
  }
}
