获取零值

题目描述

假设你有一个整数$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$所需的最小操作次数。

示例 #1

示例输入 #1

4
19 32764 10240 49

示例输出 #1

14 4 4 15

提示

让我们考虑每个$a_i$ ：

• $a_1 = 19$。你可以首先将其增加1得到$20$，然后将它乘以2 13次。你在$1 + 13 = 14$步中得到$0$。
• $a_2 = 32764$。你可以增加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次。