素数判定 (64bit)

問題文

$T$ 個のテストケースが与えられるので、それぞれについて答えてください。

非負整数 $a$ が与えられます。 $a$ が素数であれば $1$、素数でなければ $0$ を、与えられた非負整数とともに出力してください。

制約

• $1\leq T\leq 10000$
• $0\leq a_t < 2^{64}\quad(1\leq t\leq T)$
• 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

最小の行にその入力ケースのテストケース数 $T$ が、それ以降の $T$ 行には非負整数 $a_t$ が与えられる。

出力

$T$ 行出力せよ。 $t$ 行目には、入力された非負整数 $a_t$ と、それが素数か素数でないか $b_t$ （素数なら $1$、素数でなければ $0$）を出力せよ。

サンプル 1

入力

10
0
1
2
3
1387
4294967291
1713045574801
18446744066047760377
18446744073709551557
18446744073709551615

出力

0 0
1 0
2 1
3 1
1387 0
4294967291 1
1713045574801 0
18446744066047760377 0
18446744073709551557 1
18446744073709551615 0