using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Text;
namespace No3030
{
class Program
{
public static void Solve(Input input)
{
var n = input.NextInt();
var xx = input.NextLong(n);
foreach (var x in xx)
{
Console.WriteLine($"{x} {(MathEx.IsPrime(x) ? 1 : 0)}");
}
}
///
/// 最大公約数
/// 最小公倍数
/// 拡張ユークリッド互除法
///
/// 約数列挙
///
/// 素数判定
/// 素数の個数
/// 素因数分解
/// 素数列挙(エラトステネスの篩)
///
public static class MathEx
{
#region GCD / LCM
///
/// 最大公約数
/// ユークリッド互除法
///
public static long Gcd(long a, long b)
{
long r;
while ((r = a % b) != 0)
{
a = b;
b = r;
}
return b;
}
///
/// 最大公約数
///
public static long Gcd(IEnumerable nums)
=> nums.Aggregate((n, next) => n = Gcd(n, next));
///
/// 最大公約数
///
public static int Gcd(IEnumerable nums)
=> (int)Gcd(nums.Select(x => (long)x));
///
/// 最小公倍数
///
public static long Lcm(long a, long b)
=> a / Gcd(a, b) * b;
///
/// 最小公倍数
///
public static long Lcm(IEnumerable nums)
=> nums.Aggregate((n, next) => n = Lcm(n, next));
///
/// 最小公倍数
///
public static long Lcm(IEnumerable nums)
=> Lcm(nums.Select(x => (long)x));
///
/// 拡張ユークリッドの互除法
/// ax+by = gcd(a,b)の整数解
///
public static void ExtendedGcd(long a, long b, out long x, out long y)
{
long u = 0, v = 1;
x = 1; y = 0;
while (b > 0)
{
long q = a / b;
long t;
t = u;
u = x - q * u;
x = t;
t = v;
v = y - q * v;
y = t;
t = b;
b = a - q * b;
a = t;
}
}
#endregion
#region 約数列挙
///
/// 約数列挙 順番はバラバラなので注意!
///
private static IEnumerable Divisors(long n)
{
if (n < 1) yield break;
var rn = (int)(Math.Sqrt(n) + 1);
for (long i = 1; i < rn; i++)
{
if ((n % i) == 0)
{
yield return i;
if (i != (n / i)) yield return n / i;
}
}
}
///
/// 約数列挙
///
///
/// 昇順ソートするか
///
public static long[] Divisors(long n, bool needsSort = false)
{
var divs = Divisors(n).ToArray();
if (needsSort) Array.Sort(divs);
return divs;
}
#endregion
#region 素数
///
/// 素数判定
///
public static bool IsPrime(ulong n)
{
// 小さい数の時は試し割が早い気がするので分岐しておく
// ただししきい値は適当……
if (n < 100)
{
return IsPrimeTrialDiv(n);
}
else
{
return IsPrimeMillerRabin(n);
}
}
///
/// 素数判定(試し割)
///
private static bool IsPrimeTrialDiv(ulong n)
{
if (n <= 2) return n == 2;
if ((n % 2) == 0) return false;
ulong rn = (ulong)(Math.Sqrt(n) + 1);
for (ulong m = 3; m < rn; m += 2)
{
if ((n % m) == 0)
{
return false;
}
}
return true;
}
private static readonly int[] _millerRabinWitness32 = new int[] { 2, 7, 61 };
private static readonly int[] _millerRabinWitness64 = new int[] { 2, 325, 9375, 28178, 450775, 9780504, 1795265022 };
///
/// 素数判定
///
///
///
///
/// ミラー・ラビンによる
/// 本来は確率的アルゴリズムだが任意の範囲においては
/// 対応する数列すべてにクリアすれば素数と見なせる
/// 2^32 <=> {2, 7, 61}
/// 2^64 <=> {2, 325, 9375, 28178, 450775, 9780504, 1795265022}
///
/// 内部処理の関係上、本当に2^64とか極端に大きな数は計算できないことに注意
///
private static bool IsPrimeMillerRabin(ulong n)
{
if (n >= 1ul << 63)
{
throw new ArgumentOutOfRangeException(nameof(n));
}
if (n <= 2) return n == 2;
if ((n % 2) == 0) return false;
ulong n1 = n - 1;
ulong d = n1 / 2;
while ((d & 1) == 0)
{
d /= 2;
}
var witness = ((n >> 32) != 0) ? _millerRabinWitness64 : _millerRabinWitness32;
foreach (ulong m in witness)
{
if (m % n == 0) { continue; }
var t = d;
var r = ModPower(m, t, n);
while (t != n1 && r != 1 && r != n1)
{
r = ModPower(r, 2, n);
t *= 2;
}
if (r != n1 && (t & 1) == 0) { return false; }
}
return true;
}
///
/// n以下の素数判定リスト
///
public static bool[] Sieve(int n)
{
// Sieve of Eratosthenes
var sieve = Enumerable.Repeat(true, n + 1).ToArray();
if (n > 2)
{
sieve[0] = sieve[1] = false;
}
var rn = (int)(Math.Sqrt(n) + 1);
foreach (var i in Enumerable.Range(2, rn - 2))
{
if (sieve[i])
{
for (int j = 2 * i; j <= n; j += i)
{
sieve[j] = false;
}
}
}
return sieve;
}
///
/// n以下の素数リスト
///
public static IEnumerable GetPrimeList(int n)
{
var sieve = Sieve(n);
return sieve.Select((x, i) => new { X = x, I = i })
.Where(x => x.X)
.Select(x => x.I);
}
///
/// n以下の素数の個数
///
///
///
///
/// http://hidnoblog.blog46.fc2.com/?m&no=1449
///
public static long CountPrime(long n)
{
int rn = (int)Math.Sqrt(n);
var pp = GetPrimeList(rn + 1).ToArray();
long len = rn + n / (rn + 1) + 1;
var dp = new long[len + 1];
for (int i = 1; i <= rn; i++)
{
dp[i] = n / i - 1;
}
for (int i = rn + 1; i < len; i++)
{
dp[i] = len - i - 1;
}
for (int i = 0; i < pp.Length; i++)
{
for (int j = 1; j < len; j++)
{
var t = (j <= rn ? n / j : (len - j)) / pp[i];
if (t < pp[i]) { break; }
dp[j] -= dp[t > rn ? n / t : len - t] - dp[len - (pp[i] - 1)];
}
}
// dp[i]: n以下の素数をiで除した数
return dp[1];
}
///
/// 素因数分解
/// 素数(Key)がValue個ある
///
public static Dictionary Factorization(long n)
{
var map = new Dictionary();
for (long p = 2; p * p <= n; p++)
{
int count = 0;
while (n % p == 0)
{
count++;
n /= p;
}
if (count != 0) map.Add(p, count);
}
if (n > 1) map.Add(n, 1);
return map;
}
///
/// 素因数分解
/// 素数をならした配列
///
public static long[] FactorizationFlat(long n)
=> Factorization(n)
.SelectMany(x => Enumerable.Repeat(x.Key, x.Value))
.ToArray();
///
/// nと互いに素でn以下である自然数の個数
/// オイラーのファイ関数
///
public static long CoprimeCount(long n)
{
var primes = Factorization(n);
return primes.Aggregate(n, (t, u) => t - t / u.Key);
}
///
/// ルジャンドルの公式
/// n!をpで何回割り切れるか(pは素数)
///
public static long Legendres(long n, long p)
{
long count = 0;
for (long m = p; m < n; m *= p)
{
count += n / m;
}
return count;
}
#endregion
#region Misc
///
/// Mを法とする乗算
///
private static ulong ModMul(ulong a, ulong b, ulong M)
{
a %= M;
b %= M;
ulong r = 0;
if (a < ulong.MaxValue / b)
{
r = (a * b) % M;
}
else
{
// オーバーフローしそうなので地道に行なう
while (b != 0)
{
if ((b & 1) != 0) { r = (r + a) % M; }
a = (a + a) % M;
b >>= 1;
}
return r;
}
return r;
}
///
/// Mを法とする累乗
///
private static ulong ModPower(ulong a, ulong b, ulong M)
{
ulong r = 1;
while (b > 0)
{
if ((b & 1) != 0) r = ModMul(r, a, M);
a = ModMul(a, a, M);
b >>= 1;
}
return r;
}
#endregion
}
#region Main
public static void Main(string[] args)
{
// 出力が少ないときはこれをセットする方が時間かかるけれど
// そのときにTLEするのはアルゴリズムが悪いせいだし、まあ良しとする
var needsFlushOutput = true;
if (needsFlushOutput)
{
// 細かく出力しないようにする
var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
Console.SetOut(sw);
}
// 通常は引数無しで、ファイルから読み出したい場合はpath指定する
var input = new Input();
// 仮想的に標準入力をセットする
// テスト入力したまま提出することがままあるので……
#if DEBUG
input.SetText("");
#endif
Solve(input);
Console.Out.Flush();
}
#endregion
#region Competitive Template
#pragma warning disable CS0414
static readonly int MOD = (int)1e9 + 7;
static readonly int[] dx = { 1, 0, -1, 0 };
static readonly int[] dy = { 0, 1, 0, -1 };
/// 左上が原点
static readonly char[] dir = { 'R', 'U', 'L', 'D' };
#pragma warning restore CS0414
public class Input
{
// 変な改行コードがたまに混じっているので、一応セパレート指定する
// スペース単独指定の方がもちろん早い
static readonly char[] separator = { ' ', '\r', '\n' };
readonly StreamReader sr;
readonly Queue queue;
///
/// 特定のファイルから読み出したい場合はpath指定する
///
public Input(string path = "")
{
queue = new Queue();
if (string.IsNullOrEmpty(path)) { sr = new StreamReader(Console.OpenStandardInput()); }
else { sr = new StreamReader(path); }
}
///
/// 入力予約
///
public void SetText(IEnumerable items)
{
foreach (var item in items)
SetText(item);
}
///
/// 入力予約
///
public bool SetText(string s)
{
if (string.IsNullOrEmpty(s)) return false;
foreach (var elem in s.Trim().Split(separator, StringSplitOptions.RemoveEmptyEntries))
queue.Enqueue(elem);
return true;
}
///
/// 要素が存在するか
///
public bool Any() => queue.Any() || Read();
///
/// 内部queueに入力からの値をsplitして格納する
///
bool Read()
{
if (!SetText(sr.ReadLine())) return false;
if (!queue.Any()) return Read();
return queue.Any();
}
///
/// 次のstringを一つ読み込む
///
public string Next()
{
if (!queue.Any() && !Read()) return "";
return queue.Dequeue();
}
///
/// 指定個数queueにたまるまでenqueueし続ける
///
bool Accumulate(int n)
{
while (queue.Count() < n)
if (!Read()) return false;
return true;
}
public int NextInt() => int.Parse(Next());
public long NextLong() => long.Parse(Next());
public double NextDouble() => double.Parse(Next());
///
/// n個の要素をparseして、それぞれにoffsetをaddした配列を返す
///
T[] NextT(int n, T offset, Func parse, Func add)
{
if (!Accumulate(n)) return null;
var a = new T[n];
for (int i = 0; i < n; i++)
a[i] = add(parse(queue.Dequeue()), offset);
return a;
}
public string[] Next(int n) => NextT(n, "", x => x, (x, y) => x);
public int[] NextInt(int n, int offset = 0) => NextT(n, offset, int.Parse, (x, y) => x + y);
public ulong[] NextLong(int n, ulong offset = 0) => NextT(n, offset, ulong.Parse, (x, y) => x + y);
public double[] NextDouble(int n, double offset = 0.0) => NextT(n, offset, double.Parse, (x, y) => x + y);
}
static class Utils
{
public static T Max(params T[] objs) => objs.Max();
public static T Min(params T[] objs) => objs.Min();
///
/// vでfillされたT[d1][d2]配列を作成する
///
public static T[][] Create2DArray(int d1, int d2, T v)
{
return
Enumerable.Repeat(0, d1).Select(_ =>
Enumerable.Repeat(v, d2).ToArray()).ToArray();
}
///
/// vでfillされたT[d1][d2][d3]配列を作成する
///
public static T[][][] Create3DArray(int d1, int d2, int d3, T v)
{
return
Enumerable.Repeat(0, d1).Select(_ =>
Enumerable.Repeat(0, d2).Select(__ =>
Enumerable.Repeat(v, d3).ToArray()).ToArray()).ToArray();
}
}
#endregion
}
}