#include <bits/stdc++.h>
using namespace std;
const long long MAXN = 1e7 + 10;
long long v[MAXN];
long long sdiv[MAXN];
long long expv[MAXN];
long long gamb[MAXN];
vector<long long> primos;
const long long maiorzao = 1e8;
void sieve() {
  for (long long i = 0; i < MAXN; i++) {
    v[i] = -1;
    sdiv[i] = -1;
    expv[i] = 1;
    gamb[i] = -1;
  }
  for (long long i = 2; i < MAXN; i++) {
    if (v[i] == -1) primos.push_back(i);
    for (long long j = 0; j < primos.size() && i * primos[j] < MAXN; j++) {
      v[i * primos[j]] = primos[j];
      if (i % primos[j] == 0) {
        expv[i * primos[j]] = expv[i] + 1;
        break;
      } else
        expv[i * primos[j]] = 1;
    }
  }
  sdiv[1] = 1;
  for (long long i = 2; i < MAXN - 1; i++) {
    if (v[i] == -1)
      sdiv[i] = i + 1;
    else {
      long long p = i / v[i];
      if (p % v[i] != 0) {
        sdiv[i] = (v[i] + 1) * sdiv[p];
      } else {
        sdiv[i] = (sdiv[p] / (pow(v[i], expv[p] + 1) - 1)) *
                  (pow(v[i], expv[i] + 1) - 1);
      }
    }
  }
  for (long long i = 1; i < MAXN; i++) {
    if (sdiv[i] > MAXN) continue;
    if (gamb[sdiv[i]] != -1) continue;
    gamb[sdiv[i]] = i;
  }
}
int32_t main() {
  long long t;
  scanf("%lld", &t);
  sieve();
  while (t--) {
    long long a;
    scanf("%lld", &a);
    printf("%lld\n", gamb[a]);
  }
}
