Предположим, у вас есть целое число \(v\). За одну операцию вы можете:
- либо присвоить \(v = (v + 1) \bmod 32768\)
- либо присвоить \(v = (2 \cdot v) \bmod 32768\).
Вам заданы \(n\) целых чисел \(a_1, a_2, \dots, a_n\). Какое минимальное количество операций необходимо, чтобы сделать каждое \(a_i\) равным \(0\)?
Выходные данные
Выведите \(n\) чисел: \(i\)-е число должно равняться минимальному количеству операций, чтобы сделать \(a_i\) равным \(0\).
Примечание
Рассмотрим каждый \(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\) раз.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
19 32764 10240 49
|
14 4 4 15
|