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
#pragma GCC optimize("Ofast")
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#ifdef ENABLE_DEBUG
#include <debug.h>
#else
#define DEBUG(...) do {} while (0)
#endif

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using ull = unsigned long long;
using lll = __int128;
using ulll = unsigned __int128;

using ld = long double;

template<typename T, size_t N> using ar = array<T, N>;

template<typename T, typename Cmp = less<T>>
using iset = tree<T, null_type, Cmp, rb_tree_tag,
		  tree_order_statistics_node_update, allocator<T>>;

#define REPSI(name, start, stop, step) for (ll name = start; name < (ll)stop; name += step)
#define REPS(name, start, stop) REPSI(name, start, stop, 1)
#define REP(name, stop) REPS(name, 0, stop)

#define RREPSI(name, start, stop, step) for (ll name = stop-1; name >= (ll)start; name -= step)
#define RREPS(name, start, stop) RREPSI(name, start, stop, 1)
#define RREP(name, stop) RREPS(name, 0, stop)

template<typename T> void cins(T &first) { cin >> first; }
template<typename T, typename... Ts> void cins(T &first, T &second, Ts&... rest) {
  cin >> first;
  cins(second, rest...);
}

#define GET(type, ...) type __VA_ARGS__; cins(__VA_ARGS__)
#define GETI(...) GET(int, __VA_ARGS__)
#define GETLL(...) GET(ll, __VA_ARGS__)
#define GETS(...) GET(string, __VA_ARGS__)
#define GETD(...) GET(double, __VA_ARGS__)
#define GETC(...) GET(char, __VA_ARGS__)

struct hsh {
  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
    x += FIXED_RANDOM;
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
};

ull modmul(ull a, ull b, ull M) {
  ll ret = a * b - M * ull(1.L / M * a * b);
  return ret + M * (ret < 0) - M * (ret >= (ll)M);
}
ull modpow(ull b, ull e, ull mod) {
  ull ans = 1;
  for (; e; b = modmul(b, b, mod), e /= 2)
    if (e & 1) ans = modmul(ans, b, mod);
  return ans;
}

bool isPrime(ull n) {
  if (n < 2 || n % 6 % 4 != 1) return (n | 1) == 3;
  ull A[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022},
      s = __builtin_ctzll(n-1), d = n >> s;
  for (ull a : A) {   // ^ count trailing zeroes
    ull p = modpow(a%n, d, n), i = s;
    while (p != 1 && p != n - 1 && a % n && i--)
      p = modmul(p, p, n);
    if (p != n-1 && i != s) return 0;
  }
  return 1;
}

ull pollard(ull n) {
  auto f = [n](ull x) { return modmul(x, x, n) + 1; };
  ull x = 0, y = 0, t = 30, prd = 2, i = 1, q;
  while (t++ % 40 || __gcd(prd, n) == 1) {
    if (x == y) x = ++i, y = f(x);
    if ((q = modmul(prd, max(x,y) - min(x,y), n))) prd = q;
    x = f(x), y = f(f(y));
  }
  return __gcd(prd, n);
}
vector<ull> factor(ull n) {
  if (n == 1) return {};
  if (isPrime(n)) return {n};
  ull x = pollard(n);
  auto l = factor(x), r = factor(n / x);
  l.insert(l.end(), r.begin(), r.end());
  return l;
}

struct cmp {
  bool operator()(auto a, auto b) const {
    return a[0] < b[0];
    // return a[1]*b[0] < b[1]*a[0];
  }
};

ll bexp(ll b, ll e) {
  ll a = 1;
  while (e) {
    if (e&1) a *= b;
    b *= b;
    e >>= 1;
  }
  return a;
}

int main() {
  ios::sync_with_stdio(0);cin.tie(0);

  vector<bool> is_prime(1e7+1, true);
  is_prime[0] = is_prime[1] = false;
  vector<ll> primes;

  REP(p, 1e7+1) {
    if (!is_prime[p]) continue;
    primes.push_back(p);
    REPSI(i, p*p, 1e7+1, p) is_prime[i] = false;
  }

  ll mxC = 1e7;
  vector<ll> divisors(mxC, 1);

  REPS(i, 1, mxC) {
    ll v = i;
    for (ll p : primes) {
      if (p*p > v) break;

      ll den = p;
      while (v%p) {
        den *= p;
        v /= p;
      }
      divisors[i] *= (den-1)/(p-1);
      if (divisors[i] > mxC) {
        divisors[i] = 0;
        break;
      }
    }
    if (v != 1) divisors[i] *= (v*v-1)/(v-1);
    if (divisors[i] > mxC) {
      divisors[i] = 0;
      break;
    }
  }

  vector<ll> frst(mxC+1, -1);
  RREPS(i, 1, mxC) {
    frst[divisors[i]] = i;
  }

  GETI(T);
  REP(TT, T) {
    GETI(c);

    cout << frst[c] << '\n';
  }

}
