CF1661B.Getting Zero

Suppose you have an integer $v$. In one operation, you can:

• either set $v = (v + 1) \bmod 32768$
• or set $v = (2 \cdot v) \bmod 32768$.

You are given $n$ integers $a_1, a_2, \dots, a_n$. What is the minimum number of operations you need to make each $a_i$ equal to $0$?

假设你有一个整数 $v$。在一次操作中，你可以执行以下两种操作之一：

• 将 $v$ 设为 $(v + 1) \bmod 32768$；
• 或将 $v$ 设为 $(2 \cdot v) \bmod 32768$。

现给你 $n$ 个整数 $a_1, a_2, \dots, a_n$。将每个 $a_i$ 变为 $0$ 所需的最少操作次数是多少？

The first line contains the single integer $n$ ($1 \le n \le 32768$) — the number of integers.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \lt 32768$).

第一行包含一个整数 $n$（$1 \le n \le 32768$）—— 表示整数的个数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \lt 32768$）。

Print $n$ integers. The $i$-th integer should be equal to the minimum number of operations required to make $a_i$ equal to $0$.

输出 $n$ 个整数。其中第 $i$ 个整数应等于将 $a_i$ 变为 $0$ 所需的最少操作次数。

Let's consider each $a_i$:

• $a_1 = 19$. You can, firstly, increase it by one to get $20$ and then multiply it by two $13$ times. You'll get $0$ in $1 + 13 = 14$ steps.
• $a_2 = 32764$. You can increase it by one $4$ times: $32764 \rightarrow 32765 \rightarrow 32766 \rightarrow 32767 \rightarrow 0$.
• $a_3 = 10240$. You can multiply it by two $4$ times: $10240 \rightarrow 20480 \rightarrow 8192 \rightarrow 16384 \rightarrow 0$.
• $a_4 = 49$. You can multiply it by two $15$ times.

我们来分别考虑每个 $a_i$：

• $a_1 = 19$。你可以首先将其加 $1$ 得到 $20$，然后连续乘以 $2$ 共 $13$ 次，最终得到 $0$，共需 $1 + 13 = 14$ 步。
• $a_2 = 32764$。你可以连续加 $1$ 共 $4$ 次：$32764 \rightarrow 32765 \rightarrow 32766 \rightarrow 32767 \rightarrow 0$。
• $a_3 = 10240$。你可以连续乘以 $2$ 共 $4$ 次：$10240 \rightarrow 20480 \rightarrow 8192 \rightarrow 16384 \rightarrow 0$。
• $a_4 = 49$。你可以连续乘以 $2$ 共 $15$ 次。