問題文

クエリが $Q$ 個与えられます。 各クエリでは 非負整数 $a_i$ が与えられます。

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

制約

• $1 \leq Q \leq 10000$
• $0 \leq a_i \lt 2^{64}$
• 入力はすべて非負整数

入力

Q
a_1
a_2
a_3
...
a_Q

最初の行にその入力ケースのクエリ個数 $Q$ が、それ以降の $Q$ 行には非負整数 $a_i$ が与えられる。

出力

a_1 b_1
a_2 b_2
a_3 b_3
...
a_Q b_Q

$Q$ 行出力せよ。 $i\ (1\leq i\leq Q)$ 行目には、 入力された非負整数 $a_i$ と、それが素数か素数でないか $b_i$ (素数なら $1$, 素数でなければ $0$) を出力せよ。

サンプル

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