Santa Claus has N gift bags. Each bag has a weight of a1, a2, ..., < code>aN. For a uniform load on the sleigh, Santa Claus needs the weight of all bags to be the same. To achieve this, Santa Claus with his magic staff can perform one of the following operations any number of times, possibly zero times.
- Santa Claus can choose any bag and if its weight is a multiple of two, then reduce the weight by half.
- Santa Claus can choose any bag and if it is a multiple of three, then reduce the weight by three times.
Santa Claus takes 1 second for each operation.
Find the minimum total number of seconds it takes Santa Claus to reach the same weight of all the gift bags. If there is no way to achieve the goal, print the value -1.
instead
Input
The program takes as input in the first line an integer
N (2 <= N <= 1000). The second line contains
N numbers
ai - the weight of the i-th gift bag (1 <= < code>a
i <= 10
9).
Imprint
Print the answer to the problem.
Examples
| # |
Input |
Output |
| 1 |
3
1 4 3
| 3 |
| 2 |
3
2 7 6
| -1 |
| 3 |
6
1 1 1 1 1 1 |
0 |