#include <bits/stdc++.h>
using namespace std;
template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
  for (auto& i : v) is >> i;
  return is;
}
template <typename T>
ostream& operator<<(ostream& os, vector<T>& v) {
  for (auto& i : v) os << i << ' ';
  return os;
}
vector<int> genPrimes(int n) {
  vector<bool> space(n / 2, true);
  for (int i = 1; i + i + 2 * i * i < n / 2; i++) {
    for (int j = i; (i + j + 2 * i * j) < int(space.size()); j++) {
      space.at(i + j + 2 * i * j) = false;
    }
  }
  vector<int> primes;
  primes.push_back(2);
  for (int i = 1; i < n / 2; i++) {
    if (space[i]) {
      primes.push_back(2 * i + 1);
    }
  }
  return primes;
}
int nFactors(int& n, int prime) {
  int factors = 0;
  while (n % prime == 0) {
    factors++;
    n = n / prime;
  }
  return factors;
}
int factorization(int n, vector<int>& primes) {
  auto currPrime = primes.begin();
  auto factorProd = 1;
  while (n != 1) {
    auto factors = nFactors(n, *currPrime);
    int factorSum = 0;
    while (factors >= 0) {
      factorSum += pow(*currPrime, factors);
      factors--;
    }
    factorProd *= factorSum;
    currPrime = next(currPrime);
  }
  return factorProd;
}
int findEarliestN(int c, vector<int>& primes, vector<int>& mem) {
  for (int i = 1; i <= c; i++) {
    if (mem.at(i) == -1) {
      mem.at(i) = factorization(i, primes);
    }
    if (mem.at(i) == c) {
      return i;
    }
  }
  return -1;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  auto primes = genPrimes(pow(10, 7));
  vector<int> factorsMem(pow(10, 7), -1);
  int T;
  cin >> T;
  while (T--) {
    int c;
    cin >> c;
    cout << findEarliestN(c, primes, factorsMem) << '\n';
  }
}
