マルチテストについての説明はこちら (サンプル問題を確認されていない方のみお読みください。)

配点：$200$ 点

問題文

$N$ 個の非負整数 $A_1, A_2, \ldots, A_N$ と空の列 $X$ があります．

また，次の操作を何度でも行えます：

• $X$ の末尾に好きな正整数を追加する．

さらに，正整数 $n$ に対して $f(n)$ を次のように定めます：

• $f(n) := (X_k$ が $n$ の(正の)約数であるような $k$ の個数$)$．
  • より形式的には，任意の正整数 $n$ について $f(n) = |\{\, k \colon \exist_{\,x \in \Z^+} \; x X_k = n \,\}|$ が満たされる．
  • なお $1 \leq k \leq |X|$ なる整数 $k$ に対して $X$ の $k$ 番目の要素を $X_k$ と表す．

$1 \leq k \leq N$ なる任意の整数 $k$ について $f(k) = A_k$ が満たされるようにすることが目標です．

この目標が達成可能か判定し，可能な場合はそのために必要な操作回数の最小値を求めてください．

制約

• $1 \leq \Phi \leq 10^5$
• $1 \leq N$
• $\sum_{\phi} \Phi_{\phi}(N) \leq 10^6$
• $0 \leq A_i < 2^{30} \scriptsize \; (1 \leq i \leq N)$
• 入力はすべて整数

入力

各テストケースの入力は，それぞれ以下の形式で与えられる：

出力

操作によって目標が達成できるならば，それを達成するために必要な操作回数の最小値を出力せよ．
操作によって目標が達成できないならば，-1 と出力せよ．

サンプル

1
5
2 2 3 3 3

5

たとえば $X = (3, 1, 4, 1, 5)$ とすると，条件が満たされます．
$5$ 回未満の操作で目標を達成することはできないので，$5$ が答えです．

2
5
4 3 2 1 0
4
0 1 0 1

-1
1