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 read() {
  long long a = 0;
  char b = 1, c;
  do
    if ((c = getchar()) == 45) b = -1;
  while (c < 48 || c > 57);
  do a = (a << 3) + (a << 1) + (c & 15);
  while ((c = getchar()) > 47 && c < 58);
  return a * b;
}
void write(long long x) {
  if (x < 0) putchar('-'), x = -x;
  char a[10], s = 0;
  do a[s++] = x % 10 | 48;
  while (x /= 10);
  do putchar(a[--s]);
  while (s);
}
const double PI = acos(-1);
const double eps = 1e-9;
const int inf = 2000000000;
const long long infLL = 9000000000000000000;
const int lazy = int('a' - 'A');
const long long N = 1e7 + 1;
string alphabet = "abcdefghijklmnopqrstuvwxyz";
long long sum = 0, final = 0, result = 0;
template <class T = int>
T scan() {
  T res;
  std::cin >> res;
  return res;
}
bool pal(int n) {
  string lol = to_string(n);
  string s = to_string(n);
  reverse(s.begin(), s.end());
  if (s == lol) {
    return true;
  } else {
    return false;
  }
}
using namespace std;
const long long n = 4545403;
vector<long long> prime(n + 1);
void comp() {
  prime[1] = 1;
  for (int p = 2; p <= n; p++) {
    for (int i = p; i <= n; i += p) {
      prime[i] += p;
    }
    prime[p]++;
  }
}
void it_was_me_dio_hahahahahaha() {
  comp();
  unordered_map<int, int> mp;
  for (int i = prime.size() - 1; i >= 1; i--) {
    mp[prime[i]] = i;
  }
  int t = read();
  while (t--) {
    int k = read();
    if (mp[k]) {
      write(mp[k]);
      putchar('\n');
    } else {
      write(-1);
      putchar('\n');
    }
  }
}
int main() { it_was_me_dio_hahahahahaha(); }
