#include <iostream>
#include <math.h>
#include <vector>
#include <random>
#include <chrono>
#include <fstream>

using namespace std;

uint64_t powmod(uint64_t base, uint64_t exp, uint64_t modulo)
{
    unsigned res = 1;

    while (exp != 0)
    {
        if ((exp & 1) != 0)
        {
            res = (1ll * res * base) % modulo;
        }

        base = (1ll * base * base) % modulo;
        exp >>= 1;
    }

    return res;
}

vector<uint64_t> factorize(uint64_t base) {
    vector<uint64_t> result;

    uint64_t possible_divider = 2;

    while(base > 1) {
        if (base % possible_divider == 0) {
            base = base / possible_divider;
            result.push_back(possible_divider);
        }
        else {
            ++possible_divider;
        }
    }

    return result;
}

int main() {
    fstream input("primes.in", ios::in);
    fstream output("roots.out", ios::out);

    uint64_t num;
    input >> num;
    std::mt19937 gen(static_cast<unsigned>(time(nullptr)));

    for (int i = 0; i < num; ++i) {
        uint64_t prime_in;
        input >> prime_in;
        uint64_t minus_1 = prime_in - 1;
        vector<uint64_t> dividers = factorize(minus_1);
        bool root_not_found = true;
        int root = -1;

        for(int j = 0; j < 1000 && root_not_found; ++j) {
            uint64_t r = gen() % (prime_in - 3) + 2;
            uint64_t prev_divider = 0;
            bool is_root = true;

            for(int k = 0; k < dividers.size() && is_root; ++k) {
                if (dividers[k] != prev_divider) {
                    // do smth
                    uint64_t power = minus_1 / dividers[k];
                    uint64_t r_pow = powmod(r, power, prime_in);
                    prev_divider = dividers[k];

                    if (r_pow == 1) {
                        is_root = false;
                    }
                }
            }

            if (is_root) {
                root_not_found = false;
                root = r;
            }
        }

        output << root << "\n";
    }

    input.close();
    output.close();

    return 0;
}