题目描述

正整数列 $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 と出力してください。

输入格式

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

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

输出格式

答えを出力せよ。

题目大意

每次选择一个能被 $2$ 或 $3$ 整除的数，并将他除以 $2$ 或 $3$。

问将所有数变成相等的最小方案数，无解输出 $\text{-1}$。

--mfeitveer

3
1 4 3

3

3
2 7 6

-1

6
1 1 1 1 1 1

0

提示

制約

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

Sample Explanation 1

次のように操作をすると $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)$ となる。

Sample Explanation 2

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