#include <stdint.h>
#include <stdio.h>

int jacobi_symbol(int64_t a, uint64_t n) { uint64_t t; int j = 1; while (a) { if (a < 0) { a = -a; if ((n & 3) == 3) j = -j; } int s = __builtin_ctzll(a); a >>= s; if (((n & 7) == 3 || (n & 7) == 5) && (s & 1)) { j = -j; } if ((a & n & 3) == 3) { j = -j; } t = a; a = n; n = t; a %= n; if ((uint64_t)(a) > n / 2) { a -= n; } } return n == 1 ? j : 0; }
uint64_t gcd64(uint64_t a, uint64_t b) { if (!a || !b) { return a | b; } uint64_t t; uint64_t sh = __builtin_ctzll(a | b); a >>= __builtin_ctzll(a); do { b >>= __builtin_ctzll(b); if (a > b) t = a, a = b, b = t; b -= a; } while (b); return a << sh; }
uint64_t remain_sqrt(uint64_t x) { if (x == 0) { return 0; } uint32_t lz = __builtin_clzll(x); uint64_t n = 32 - (lz >> 1); uint64_t s = (lz >> 1) << 1; uint64_t t = n << 1; __uint128_t a = (__uint128_t)x; __uint128_t b = ((__uint128_t)1ull << 62) >> s; __uint128_t c = ((__uint128_t)1ull << 64) >> s; __uint128_t d = (((__uint128_t)1ull << 64) - 1) >> s; __uint128_t e = ((((__uint128_t)1ull << 64) - 1) << 65) >> s; for (int _ = 0; _ < n; ++_) { if (a >= b) { a -= b; b = ((b + b) & e) + c + (b & d); } else { b = ((b + b) & e) + (b & d); } a <<= 2; } return a >> t; }

uint64_t mr64(__uint128_t A, uint64_t n, uint64_t ninv) { uint64_t y = (uint64_t)(A >> 64) - (uint64_t)(((__uint128_t)((uint64_t)A * ninv) * n) >> 64); return (int64_t)y < 0 ? y + n : y; }
uint64_t to_m64(uint64_t a, uint64_t n, uint64_t ninv, uint64_t r2) { return mr64((__uint128_t)a * r2, n, ninv); }
uint64_t from_m64(uint64_t mra, uint64_t n, uint64_t ninv) { return mr64((__uint128_t)mra, n, ninv); }
uint64_t add_m64(uint64_t mra, uint64_t mrb, uint64_t n) { return mra >= n - mrb ? mra + mrb - n : mra + mrb; }
uint64_t sub_m64(uint64_t mra, uint64_t mrb, uint64_t n) { return mra >= mrb ? mra - mrb : mra + n - mrb; }
uint64_t min_m64(uint64_t mra, uint64_t n) { return sub_m64(0, mra, n); }
uint64_t mul_m64(uint64_t mra, uint64_t mrb, uint64_t n, uint64_t ninv) { return mr64((__uint128_t)mra * mrb, n, ninv); }
uint64_t twice_m64(uint64_t mra, uint64_t n) { return (mra <<= 1) >= n ? (mra - n) : mra; }
uint64_t half_m64(uint64_t mra, uint64_t n) { return (mra & 1) ? ((mra + n) >> 1) : (mra >> 1); }

int is_prime(uint64_t n)
{
    {
        if (~n & 1) return n == 2;
        if (n < 4) return n == 3;
        if (gcd64(15, n) != 1) return 0;
    }

    uint64_t r = (uint64_t)-1ull % n + 1;
    uint64_t r2 = (__uint128_t)(__int128_t)-1 % n + 1;
    uint64_t ninv = n;
    for (int _ = 0; _ < 5; ++_) ninv *= 2 - ninv * n;
    {
        uint64_t d = (n - 1) << __builtin_clzll(n - 1);
        uint64_t t = twice_m64(r, n);
        for (d <<= 1; d; d <<= 1)
        {
            t = mul_m64(t, t, n, ninv);
            if (d >> 63) t = twice_m64(t, n);
        }
        if (t != r)
        {
            uint64_t x = (n - 1) & -(n - 1);
            uint64_t rev = min_m64(r ,n);
            for (x >>= 1; t != rev; x >>= 1)
            {
                if (x == 0)
                    return 0;
                t = mul_m64(t, t, n, ninv);
            }
        }
    }
    {
        int64_t D = 5;
        for (int i = 0; jacobi_symbol(D, n) != -1 && i < 64; ++i)
        {
            if (i == 32)
                if (remain_sqrt(n) == 0)
                    return 0;
            if (i & 1) D -= 2;
            else       D += 2;
            D = -D;
        }
        uint64_t Q = to_m64(((D < 0) ? ((1 - D) / 4 % n) : (n - (D - 1) / 4 % n)), n, ninv, r2);
        uint64_t u = r, v = r, Qn = Q;
        uint64_t k = (n + 1) << __builtin_clzll(n + 1);
        D %= (int64_t)n;
        D = to_m64(((D < 0) ? ((int64_t)n + D) : D), n, ninv ,r2);
        for (k <<= 1; k; k <<= 1) {
            u = mul_m64(u, v, n, ninv);
            v = sub_m64(mul_m64(v, v, n, ninv), add_m64(Qn, Qn, n), n);
            Qn = mul_m64(Qn, Qn, n, ninv);
            if (k >> 63) {
                uint64_t uu = add_m64(u, v, n);
                uu = half_m64(uu, n);
                v = add_m64(mul_m64(D, u, n, ninv), v, n);
                v = half_m64(v, n);
                u = uu;
                Qn = mul_m64(Qn, Q, n, ninv);
            }
        }
        if (u == 0 || v == 0)
            return 1;
        uint64_t x = (n + 1) & ~n;
        for (x >>= 1; x; x >>= 1)
        {
            u = mul_m64(u, v, n, ninv);
            v = sub_m64(mul_m64(v, v, n, ninv), add_m64(Qn, Qn, n), n);
            if (v == 0)
                return 1;
            Qn = mul_m64(Qn, Qn, n, ninv);
        }
    }

    return 0;
}

uint64_t in(void) { uint64_t c, x = 0; while (c = getchar_unlocked(), c < 48 || c > 57); while (47 < c && c < 58) { x = x * 10 + c - 48; c = getchar_unlocked(); } return x; }
void out(uint64_t x) { if (x >= 10) out((((__uint128_t)x * 14757395258967641293ull) >> 3) >> 64); putchar_unlocked(x - ((((__uint128_t)x * 14757395258967641293ull) >> 3) >> 64) * 10 + 48); }

int main(void)
{
    uint64_t Q = in();
    while (Q--) {
        uint64_t x = in();
        out(x);
        putchar_unlocked(' ');
        out(is_prime(x));
        putchar_unlocked('\n');
    }
    return 0;
}