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>
#pragma GCC optimize(2)
using namespace std;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
struct InputOutputStream {
  enum { SIZE = 1000001 };
  char ibuf[SIZE], *s, *t, obuf[SIZE], *oh;
  bool eof;
  InputOutputStream() : s(), t(), oh(obuf), eof(false) {}
  ~InputOutputStream() { fwrite(obuf, 1, oh - obuf, stdout); }
  explicit operator bool() const { return static_cast<bool>(eof == false); }
  inline char read() {
    if (s == t) t = (s = ibuf) + fread(ibuf, 1, SIZE, stdin);
    return s == t ? -1 : *s++;
  }
  inline InputOutputStream &operator>>(char *x) {
    static char c;
    for (c = read(); isspace(c); c = read())
      if (c == -1) {
        eof = true;
        return *this;
      }
    for (; !isspace(c); c = read()) *x = c, ++x;
    *x = 0;
    return *this;
  }
  template <typename T>
  inline InputOutputStream &operator>>(T &x) {
    static char c;
    static bool iosig;
    for (c = read(), iosig = false; !isdigit(c); c = read()) {
      if (c == -1) {
        eof = true;
        return *this;
      }
      iosig |= c == '-';
    }
    for (x = 0; isdigit(c); c = read()) x = x * 10 + (c ^ '0');
    if (iosig) x = -x;
    return *this;
  }
  inline void print(char c) {
    if (oh == obuf + SIZE) {
      fwrite(obuf, 1, SIZE, stdout);
      oh = obuf;
    }
    *oh++ = c;
  }
  template <typename T>
  inline void print(T x) {
    static int buf[23], cnt;
    if (x != 0) {
      if (x < 0) print('-'), x = -x;
      for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 | 48;
      while (cnt) print((char)buf[cnt--]);
    } else
      print('0');
  }
  template <typename T>
  inline InputOutputStream &operator<<(const T &x) {
    print(x);
    return *this;
  }
  inline void print(const char *x) {
    for (; *x; x++) print(*x);
  }
  inline void print(char *x) {
    for (; *x; x++) print(*x);
  }
} io;
const int maxn = 1e7 + 5;
long long prime[maxn], id;
bool is_prime[maxn];
int dx[maxn];
int mp[maxn];
void euler(int n) {
  id = 0;
  memset(is_prime, true, sizeof(is_prime));
  is_prime[1] = false;
  dx[1] = 1;
  mp[dx[1]] = 1;
  for (int i = 2; i <= n; ++i) {
    if (is_prime[i]) {
      prime[++id] = i;
      dx[i] = 1 + i;
      if (dx[i] <= n) {
        if (mp[dx[i]] == 0)
          mp[dx[i]] = i;
        else
          mp[dx[i]] = min(i, mp[dx[i]]);
      }
    }
    for (int j = 1; j <= id && i * prime[j] <= n; ++j) {
      int tmp = i * prime[j];
      is_prime[tmp] = false;
      if (i % prime[j] == 0) {
        dx[tmp] = dx[i] * prime[j] + dx[i / prime[j]];
        if (dx[tmp] <= n) {
          if (mp[dx[tmp]] == 0)
            mp[dx[tmp]] = tmp;
          else
            mp[dx[tmp]] = min(tmp, mp[dx[tmp]]);
        }
        break;
      }
      dx[tmp] = dx[i] * dx[prime[j]];
      if (dx[tmp] <= n) {
        if (mp[dx[tmp]] == 0)
          mp[dx[tmp]] = tmp;
        else
          mp[dx[tmp]] = min(tmp, mp[dx[tmp]]);
      }
    }
  }
}
int t;
int c;
signed main() {
  io >> t;
  int n = 1e7;
  euler(n);
  while (t--) {
    io >> c;
    if (mp[c] == 0) {
      io << "-1\n";
    } else {
      io << mp[c] << '\n';
    }
  }
  return 0;
}
