#include <bits/stdc++.h>
using namespace std;
const int SVSZ = 2400000;
typedef long long (*func_ptr)(int&, int&, int&);
int spf[SVSZ];
int hpp[SVSZ];
int hpc[SVSZ];
long long func[SVSZ];
vector<int> primes;
int ONE = 1;
long long divSum(int& HPP, int& HPC, int& SPF) {
  long long h = HPP, s = SPF;
  return (h * s - 1) / (s - 1);
}
void buildSieveMult(func_ptr Mult) {
  spf[0] = spf[1] = hpp[1] = func[1] = 1;
  hpp[0] = hpc[0] = hpc[1] = func[0] = 0;
  for (int i = 2; i < SVSZ; i++) {
    if (spf[i] == 0) {
      primes.push_back(i);
      spf[i] = i;
      func[i] = Mult(i, ONE, i);
      hpp[i] = i;
      hpc[i] = 1;
    }
    for (int j = 0; j < (int)primes.size() && i * primes[j] < SVSZ; j++) {
      spf[i * primes[j]] = primes[j];
      if (i % primes[j]) {
        func[i * primes[j]] = (long long)func[i] * (long long)func[primes[j]];
        hpp[i * primes[j]] = primes[j];
        hpc[i * primes[j]] = 1;
      } else {
        hpp[i * primes[j]] = primes[j] * hpp[i];
        hpc[i * primes[j]] = 1 + hpc[i];
        func[i * primes[j]] =
            (long long)func[i / hpp[i]] *
            Mult(hpp[i * primes[j]], hpc[i * primes[j]], primes[j]);
        break;
      }
    }
  }
}
vector<int> res(10445761, -1);
int main() {
  buildSieveMult(divSum);
  for (int i = 1; i < SVSZ; i++) {
    if (res[func[i]] != -1) {
      continue;
    }
    res[func[i]] = i;
  }
  int t;
  cin >> t;
  while (t--) {
    int c;
    cin >> c;
    cout << res[c] << '\n';
  }
  cin.ignore(2);
  return 0;
}
