B. Получение нуля
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Предположим, у вас есть целое число $$$v$$$. За одну операцию вы можете:

  • либо присвоить $$$v = (v + 1) \bmod 32768$$$
  • либо присвоить $$$v = (2 \cdot v) \bmod 32768$$$.

Вам заданы $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$. Какое минимальное количество операций необходимо, чтобы сделать каждое $$$a_i$$$ равным $$$0$$$?

Входные данные

В первой строке задано одно целое число $$$n$$$ ($$$1 \le n \le 32768$$$) — количество чисел.

Во второй строке заданы $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i < 32768$$$).

Выходные данные

Выведите $$$n$$$ чисел: $$$i$$$-е число должно равняться минимальному количеству операций, чтобы сделать $$$a_i$$$ равным $$$0$$$.

Пример
Входные данные
4
19 32764 10240 49
Выходные данные
14 4 4 15
Примечание

Рассмотрим каждый $$$a_i$$$:

  • $$$a_1 = 19$$$. Вы можете, сначала, увеличить его на единицу и получить $$$20$$$, а потом умножить его на два $$$13$$$ раз. Вы получите $$$0$$$ за $$$1 + 13 = 14$$$ шагов.
  • $$$a_2 = 32764$$$. Вы можете увеличить число на единицу $$$4$$$ раза: $$$32764 \rightarrow 32765 \rightarrow 32766 \rightarrow 32767 \rightarrow 0$$$.
  • $$$a_3 = 10240$$$. Вы можете умножить его на два $$$4$$$ раза: $$$10240 \rightarrow 20480 \rightarrow 8192 \rightarrow 16384 \rightarrow 0$$$.
  • $$$a_4 = 49$$$. Вы можете умножить его на два $$$15$$$ раз.