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;
long long int i, j, a, k, b, c, n, t = 1, m, p, q, d, e, f, y, g, z, h, r, l, x,
                                   u, o;
long double aa, bb, ee, dd, ff, kk, gg, cc;
vector<long long int> v, s, vv;
vector<long long int> ss, pp;
map<long long int, long long int> ta, pa, sa, ma;
map<pair<long long int, long long int>, long long int> me, he, mem;
map<string, long long int> se;
priority_queue<long long int> aq, tq, pq, nq, mq, xq;
string st, et, ft, pt, ct;
deque<char> de, ne;
set<long long int> li, si;
long long int ar[3205];
void sieve() {
  for (i = 4; i <= 3200; i = i + 2) {
    ar[i] = 1;
  }
  for (i = 3; i * i <= 3200; i = i + 2) {
    if (ar[i] == 0) {
      for (j = i * i; j <= 3200; j = j + (2 * i)) {
        ar[j] = 1;
      }
    }
  }
  for (i = 2; i <= 3200; i++) {
    if (ar[i] == 0) v.push_back(i);
  }
}
int main() {
  sieve();
  for (i = 1; i < 1000000; i++) {
    b = i;
    e = 1;
    for (j = 0; v[j] * v[j] <= b && j < v.size(); j++) {
      if (b % v[j] == 0) {
        f = 0;
        while (b % v[j] == 0) {
          b = b / v[j];
          f++;
        }
        c = pow(v[j], f + 1) - 1;
        d = c / (v[j] - 1);
        e = e * d;
      }
    }
    if (b > 1) c = pow(b, 2) - 1, d = c / (b - 1), e = e * d;
    if (ma[e] == 0)
      ma[e] = i;
    else
      ma[e] = min(ma[e], i);
  }
  cin >> t;
  p = 0;
  while (t--) {
    cin >> n;
    if (ma[n] == 0)
      cout << -1 << endl;
    else
      cout << ma[n] << endl;
  }
};
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
