1304 - 掛けても素数！？

問題

$N$ 個の整数が与えられる。$i$ $(1 \leq i \leq N)$ 番目の整数は $a_i$ である。
各 $a_i$ について、$a_i \times k$ が素数となる正整数 $k$ を出力せよ。
ただし、そのような $k$ が複数存在する場合はその中で最も値の小さなものを出力し、そのような $k$ が存在しない場合はNAと出力せよ。

入力

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

$N$
$a_1$
$a_2$
$\vdots$
$a_N$

出力

出力は $N$ 行からなる。
各 $a_i$ に対する答えを改行区切りで出力せよ。

制約

• $1 \leq N \leq 10^6$
• $1 \leq a_i \leq 6 \times 10^6$
• 入力は全て整数である。

入出力例

入力例１

5
12
7
5
57
2

出力例１

NA
1
1
NA
1

注意

C++において、通常のcin,coutだとTLEする場合があります。

cin.tie(nullptr);
ios_base::sync_with_stdio(false);

で高速化しましょう。