Patchouli является магическим талисманом. Изначально у него \(n\) магических жетонов. Их магическая сила может быть представлена положительными целыми числами \(a_1, a_2, \ldots, a_n\).
Patchouli может выполнять следующие две операции с жетонами.
- Слияние: Patchouli выбирает два жетона, убирает их и создает новый жетон с магической силой, равной сумме двух выбранных жетонов.
- Сокращение: Patchouli выбирает жетон с четным значением магической силы \(x\), удаляет его и создает новый жетон с магической силой, равной \(\frac{x}{2}\).
Жетоны наиболее эффективны, когда они имеют нечетное значение магической силы. Пожалуйста, помогите Patchouli найти минимальное количество операций, необходимых ему, чтобы все жетоны имели нечетное значение магической силы.
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальное количество операций, которое нужно Patchouli, чтобы все жетоны имели нечетное значение магической силы.
Можно показать, что при заданных ограничениях требуемая последовательность операций существует.
Примечание
В первом наборе входных данных \(a\) изначально состоит только из нечетных чисел.
Во втором наборе входных данных выберите жетоны с магической силой \(1\) и \(2\) и выполните слияние. Теперь \(a=[1,3]\), оба нечетные числа.
В третьем наборе входных данных сначала выберите жетоны с магической силой \(2\) и \(8\) и выполните слияние. Теперь \(a=[4,10]\). Дальше выберите жетон с магической силой \(10\) и выполните сокращение. Теперь \(a=[4,5]\). Выберите жетоны с магической силой \(4\) и \(5\) и выполните слияние. Теперь \(a=[9]\), а \(9\) — нечетное число.
Можно показать, что вы не можете получить все магические силы нечетными числами менее чем за \(3\) хода, поэтому ответ равен \(3\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2
1 9
3
1 1 2
3
2 4 8
3
1049600 33792 1280
|
0
1
3
10
|