У Деда Мороза есть N мешков с подарками. Каждый мешок имеет вес a1, a2, ..., aN. Для равномерной нагрузки на сани Деду Морозу необходимо, чтобы вес всех мешков был одинаковым. Чтобы этого добиться, Дед Мороз своим волшебным посохом может выполнить одну из следующих операций любое количество раз, возможно ноль раз.
- Дед Мороз может выбрать любой мешок и если его вес кратен двум, то уменьшить вес в два раза.
- Дед Мороз может выбрать любой мешок и если его кратен трем, то уменьшить вес в три раза.
На каждую операцию у Деда Мороза уходит 1 секунда.
Найдите минимальное общее количество секунд, которое необходимо Деду Морозу, для достижения одинакового веса всех мешков с подарками. Если нет способа достичь цели, выведите вместо этого значение -1.
Входные данные
Программа получает на вход в первой строке целое число
N (2 <= N <= 1000). Во второй строке записаны
N чисел
ai - вес i-го мешка с подарками (1 <=
ai <= 10
9).
Выходные данные
Выведите ответ на задачу.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
3
1 4 3 |
3 |
| 2 |
3
2 7 6 |
-1 |
| 3 |
6
1 1 1 1 1 1 |
0 |