009 - 掛けても素数！？

時間制限 1 秒 / メモリ制限 256 MB / 得点 100 / x 5 /

TLE
1sec
MLE
256MB
得点
100
bool型の配列とvector<bool>とでは、実行時間やメモリの使用量が異なります。
この問題では、vector<bool>を使用してください。
↑bool[]でもACできるときとできないときがあるっぽい？（メモリ制限を変更してもいいかも）

問題

$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);

で高速化しましょう。