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>
const int N = 1e5 + 5;
const int mod = 1e9 + 7;
const long long int int_max = 1e18;
const long long int int_min = -1e18;
const long double PI = acos(-1);
using namespace std;
map<long long int, long long int> m, vis, ans;
long long int power(long long int x, long long int y) {
  long long int temp;
  if (y == 0) return 1;
  temp = power(x, y / 2);
  if (y % 2 == 0)
    return temp * temp;
  else {
    if (y > 0)
      return x * temp * temp;
    else
      return (temp * temp) / x;
  }
}
long long int factorize(long long n) {
  int count = 0;
  while (!(n % 2)) {
    n >>= 1;
    count++;
  }
  map<long long int, long long int> m;
  if (count) m[2] = count;
  for (long long i = 3; i <= sqrt(n); i += 2) {
    count = 0;
    while (n % i == 0) {
      count++;
      n = n / i;
    }
    if (count) m[i] = count;
  }
  if (n > 2) m[n] = 1;
  long long int sum = 1;
  vector<long long int> v;
  for (auto i : m) {
    long long int sum1 = 0;
    for (long long int j = 0; j <= i.second; j++) {
      sum1 += power(i.first, j);
    }
    v.push_back(sum1);
  }
  for (long long int i = 0; i < v.size(); i++) {
    sum *= v[i];
  }
  return sum;
}
void solve() {
  long long int n;
  cin >> n;
  if (vis[n] == 0) {
    cout << -1 << '\n';
  } else {
    cout << ans[n] << '\n';
  }
}
int main() {
  ios::sync_with_stdio(false), cin.tie(NULL);
  ans[1] = 1;
  vis[1] = 1;
  for (long long int i = 1; i <= 500000; i++) {
    long long int a1 = factorize(i);
    if (vis[a1] == 0) {
      vis[a1] = 1;
      ans[a1] = i;
    }
  }
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
}
