配点 : $400$ 点

問題文

正整数列 $A=(a_1,a_2,\ldots,a_N)$ が与えられます。 あなたは以下の操作のうち $1$ つを選んで行うことを $0$ 回以上何度でも繰り返せます。

• $1 \leq i \leq N$ かつ $a_i$ が $2$ の倍数であるような整数 $i$ を選び、$a_i$ を $\frac{a_i}{2}$ に置き換える
• $1 \leq i \leq N$ かつ $a_i$ が $3$ の倍数であるような整数 $i$ を選び、$a_i$ を $\frac{a_i}{3}$ に置き換える

あなたの目標は $A$ が $a_1=a_2=\ldots=a_N$ を満たす状態にすることです。 目標を達成するために必要な操作の回数の最小値を求めてください。ただし、どのように操作を行っても目標を達成できない場合、代わりに -1 と出力してください。

制約

• $2 \leq N \leq 1000$
• $1 \leq a_i \leq 10^9$
• 入力はすべて整数

入力

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

$N$

$a_1$ $a_2$ $\ldots$ $a_N$

出力

答えを出力せよ。

3
1 4 3

3

次のように操作をすると $3$ 回で目標を達成でき、これが最小の回数です。

• $a_i$ が $2$ の倍数であるような整数 $i$ として $2$ を選び、$a_2$ を $\frac{a_2}{2}$ に置き換える。$A$ は $(1,2,3)$ となる。
• $a_i$ が $2$ の倍数であるような整数 $i$ として $2$ を選び、$a_2$ を $\frac{a_2}{2}$ に置き換える。$A$ は $(1,1,3)$ となる。
• $a_i$ が $3$ の倍数であるような整数 $i$ として $3$ を選び、$a_3$ を $\frac{a_3}{3}$ に置き換える。$A$ は $(1,1,1)$ となる。

3
2 7 6

-1

どのように操作を行っても目標を達成できません。

6
1 1 1 1 1 1

0