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 long long inf = 1e16;
const int MOD = 4194304;
typedef decay<decltype(MOD)>::type T;
struct mi {
  T val;
  explicit operator T() const { return val; }
  mi() { val = 0; }
  mi(const long long& v) {
    val = (-MOD <= v && v <= MOD) ? v : v % MOD;
    if (val < 0) val += MOD;
  }
  friend ostream& operator<<(ostream& os, const mi& a) { return os << a.val; }
  friend bool operator==(const mi& a, const mi& b) { return a.val == b.val; }
  friend bool operator!=(const mi& a, const mi& b) { return !(a == b); }
  friend bool operator<(const mi& a, const mi& b) { return a.val < b.val; }
  mi operator-() const { return mi(-val); }
  mi& operator+=(const mi& m) {
    if ((val += m.val) >= MOD) val -= MOD;
    return *this;
  }
  mi& operator-=(const mi& m) {
    if ((val -= m.val) < 0) val += MOD;
    return *this;
  }
  mi& operator*=(const mi& m) {
    val = (long long)val * m.val % MOD;
    return *this;
  }
  friend mi pow(mi a, long long p) {
    mi ans = 1;
    assert(p >= 0);
    for (; p; p /= 2, a *= a)
      if (p & 1) ans *= a;
    return ans;
  }
  friend mi inv(const mi& a) {
    assert(a != 0);
    return pow(a, MOD - 2);
  }
  mi& operator/=(const mi& m) { return (*this) *= inv(m); }
  friend mi operator+(mi a, const mi& b) { return a += b; }
  friend mi operator-(mi a, const mi& b) { return a -= b; }
  friend mi operator*(mi a, const mi& b) { return a *= b; }
  friend mi operator/(mi a, const mi& b) { return a /= b; }
};
long long sieve[10000005];
long long dp[1000001];
long long ret[1000001];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  memset(sieve, 0, sizeof(sieve));
  memset(ret, 0, sizeof(ret));
  sieve[0] = 0;
  sieve[1] = 1;
  ret[0] = 0;
  ret[1] = 1;
  for (long long i = 2; i <= 1e7; i++) {
    if (sieve[i] == 0) {
      sieve[i] = i;
      if (i * i <= 1e7) {
        for (long long j = i * i; j <= 1e7; j += i) {
          if (sieve[j] == 0) {
            sieve[j] = i;
          }
        }
      }
    }
  }
  dp[0] = 0;
  dp[1] = 1;
  for (long long i = 2; i <= 1e7; i++) {
    if (sieve[i] == i) {
      dp[i] = i + 1;
    } else {
      long long nxt = dp[i] / sieve[i];
      if (nxt == sieve[i]) {
        dp[i] = dp[nxt] + i;
      } else {
        dp[i] = dp[nxt] * (sieve[i] + 1);
      }
    }
    if (i == 2) {
      cout << dp[i] << endl;
    }
    if (ret[dp[i]] == -1) {
      ret[dp[i]] = i;
    }
    ret[dp[i]] = min(ret[dp[i]], i);
  }
  long long n;
  cin >> n;
  for (long long i = 0; i < n; i++) {
    long long c;
    cin >> c;
    if (ret[c] == 0) {
      cout << -1 << endl;
    } else {
      cout << ret[c] << endl;
    }
  }
}
