#include <assert.h>
#include <math.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

typedef int8_t i8;
typedef int16_t i16;
typedef int32_t i32;
typedef int64_t i64;
typedef __int128_t i128;
typedef uint8_t u8;
typedef uint16_t u16;
typedef uint32_t u32;
typedef uint64_t u64;
typedef __uint128_t u128;

static i64 Scanner(void) {
  i64 x = 0, f = 1, c;
  while (c = getchar_unlocked(), c < 48 || c > 57) if (c == 45) f = -f;
  while (47 < c && c < 58) {
    x = x * 10 + c - 48;
    c = getchar_unlocked();
  }
  return f * x;
}
static u64 ScannerU(void) {
  u64 x = 0, c;
  while (c = getchar_unlocked(), c < 48 || c > 57);
  while (47 < c && c < 58) {
    x = x * 10 + c - 48;
    c = getchar_unlocked();
  }
  return x;
}
static void Printer(i64 x) {
  if (x < 0) {
    putchar_unlocked('-');
    x = -x;
  }
  if (x >= 10) {
    Printer(x / 10);
  }
  putchar_unlocked(x - x / 10 * 10 + 48);
}
static void PrinterU(u64 x) {
  if (x >= 10) {
    Printer(x / 10);
  }
  putchar_unlocked(x - x / 10 * 10 + 48);
}
static void newline(void) {
  putchar_unlocked('\n');
}

static inline u64 ctz(u64 n) { return __builtin_ctzll(n); }
static inline u64 clz(u64 n) { return __builtin_clzll(n); }
static inline u64 popcnt(u64 n) { return __builtin_popcountll(n); }
u64 binary_gcd(u64 u, u64 v) {
  int shl = 0;
  while (u && v && u != v) {
    bool eu = !(u & 1);
    bool ev = !(v & 1);
    if (eu && ev) {
      ++shl;
      u >>= 1;
      v >>= 1;
    }
    else if (eu && !ev) u >>= 1;
    else if (!eu && ev) v >>= 1;
    else if (u >= v) u = (u - v) >> 1;
    else {
      int tmp = u;
      u = (v - u) >> 1;
      v = tmp;
    }
  }
  return !u ? v << shl : u << shl;
}
u64 binary_lcm(u64 u, u64 v) {
  return u / binary_gcd(u, v) * v;
}
i32 ceil_pow2_32(i32 n) {
  return n <= 1 ? 0 : 32 - __builtin_clz(n - 1);
}
i64 ceil_pow2_64(i64 n) {
  return n <= 1 ? 0 : 64 - __builtin_clzl(n - 1);
}

static u64 _rng = 88172645463325252ULL;
u64 next_rand(void) {
  _rng = _rng ^ (_rng << 7);
  return _rng = _rng ^ (_rng >> 9);
}

typedef u64 m64;

u64 mul_inv(u64 n) {
  u64 x = 1;
  for (int i = 6; i > 0; --i) {
    x = x * (2 - x * n);
  }
  return x;
}
m64 calc_mod(u64 m) {
  return m;
}
m64 calc_inv(u64 m) {
  return mul_inv(calc_mod(m));
}
m64 calc_r2(u64 m) {
  return -(u128)(calc_mod(m)) % calc_mod(m);
}
m64 MR(u128 x, m64 mod, m64 inv) {
  m64 y = (u64)(x >> 64) - (u64)(((u128)((u64)x * inv) * mod) >> 64);
  return (i64)y < 0 ? y + mod : y;
}
m64 toM64(u64 w, m64 mod, m64 inv, m64 r2) { return MR((u128)w * r2, mod, inv); }
u64 fromM64(m64 x, m64 mod, m64 inv) { return MR((u128)x, mod, inv); }
m64 addmod(m64 x, m64 y, m64 mod) {
  return (x + y >= mod) ? x + y - mod: x + y;
}
m64 submod(m64 x, m64 y, m64 mod) {
  return (i64)(x - y) < 0 ? x - y + mod : x - y;
}
m64 mulmod(m64 x, m64 y, m64 mod, m64 inv) {
  return MR((u128)x * y, mod, inv);
}
m64 powmod(m64 x, int i, m64 mod, m64 inv, m64 r2) {
  m64 ret = toM64(1, mod, inv, r2);
  for (; i; i >>= 1) {
    if (i & 1) ret = mulmod(ret, x, mod, inv);
    x = mulmod(x, x, mod, inv);
  }
  return ret;
}

bool is_prime(u64 n) {
  if (n < 10) return n == 2 || n == 3 || n == 5 || n == 7;
  if (n % 2 == 0) return false;
  u64 mod = calc_mod(n);
  u64 inv = calc_inv(n);
  u64 r2 = calc_r2(n);
  u64 m = n - 1;
  u64 s = __builtin_ctzll(m);
  u64 d = m >> s;
  m64 one = toM64(1, mod, inv, r2);
  m64 mone = toM64(m, mod, inv, r2);
  u64 a[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
  for (int i = 0; i < 7; i++) {
    if (n <= a[i]) break;
    m64 r = powmod(toM64(a[i], mod, inv, r2), d, mod, inv, r2);
    if (r == one || r == mone) continue;
    int t = s;
    for (; t; t--) {
      r = mulmod(r, r, mod, inv);
      if (r == mone) break;
    }
    if (!t) return false;
  }
  return true;
}

void Main(void) {
  u64 Query = ScannerU();
  while (Query--) {
    u64 x = ScannerU();
    PrinterU(x);
    putchar_unlocked(' ');
    PrinterU(is_prime(x));
    newline();
  }
}

int main() {
  Main();
  return 0;
}