1818 - おみやげの分解

時間制限 1 秒 / メモリ制限 64 MB / 得点 1 / Writer Koba_gochiusa / x 5 / 統計 /


TLE
1sec
MLE
64MB
得点
1

問題

※この問題文はフィクションです

※上の注意書きはフィクションです

※上の注意書きはフィクションです

偶数好きのKくんは弁天島に旅行に来ています.
せっかくの旅行なので, Kくんの親友であり, 素数好きのWくんにおみやげを渡そうと考えました.
しかし, 弁天島にはこれといったおみやげはなかったので, いくつかの偶数を持ち帰りました.

後日, Kくんからおみやげを受け取ったWくんは, 偶数より素数のほうがが好みのため, 総和がもらった偶数に等しいような, いくつかの素数に分解しようとしています.
Wくんも人間なので, あまりバラバラにしては申し訳ないと思い, なるべく少ない個数に分けることにしました.

1行目に, WくんがKくんからもらった偶数の個数$n$が与えられます.
その後$n$行にわたって, もらった偶数 $K_{i}$が与えられます.

それぞれの$K_{i}$を最小でいくつの素数に分解できるか求めてください.
素数に分解できない場合は, -1を出力してください.

入力

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

$n$
$K_{0}$
$K_{1}$
:
$K_{n-1}$

出力

出力の最後に改行を入れること。

制約

全ての入出力ケースについて以下を満たす。

  • $0 \leq N \leq 2×10^{5}$
  • $2 \leq K_{i} \leq 10^{18}$

入出力例

入力例1

1
2

出力例1

1

2は素数です。
2だけで表すことができます。


入力例2

2
4
6

出力例2

2
2

4 = 2 + 2
6 = 3 + 3
である。