题目描述

给定一个整数 $v$。你可以对整数 $v$ 进行若干次操作。每次操作，你可以：

• 操作1：令 $v \leftarrow (v + 1) \text{ mod } 32768$，或
• 操作2：令 $v \leftarrow (2 \cdot v) \text{ mod } 32768$

（即：每次操作从上述两种类型的操作中任选一个操作执行）。

这里，$\text{mod}$ 运算指的是 模运算 ，$a \text{ mod } b$ 的结果就是 $a \div b$ 的余数。

现在给你一个长度为 $n$ 的数列 $a_1, a_2, \ldots, a_n$。对于数列中的每个元素 $a_i$，你需要回答出至少需要执行几次操作能够使 $a_i$ 变成 $0$ ？

输入格式

第一行，一个整数 $n(1 \le n \le 32768)$。

第二行，$n$ 个整数 $a_1, a_2, \ldots, a_n(0 \le a_i \lt 32768)$。

输出格式

输出共一行，包含 $n$ 个整数，两两之间以一个空格分隔。其中第 $i$ 个整数表示将 $a_i$ 变为 $0$ 至少需要执行几次操作。

4
19 32764 10240 49

14 4 4 15

说明/提示

样例解释

• $a_1 = 19$，先对其进行 $$ 次操作1，再对其进行 $13$ 次操作2，它会变成 $0$；
• $a_2 = 32764$，对其进行 $4$ 次操作1（$32764 \rightarrow 32765 \rightarrow 32766 \rightarrow 32767 \rightarrow 0$），它会变成 $0$；
• $a_3 = 10240$，对其进行 $4$ 次操作2（$10240 \rightarrow 20480 \rightarrow 8192 \rightarrow 16384 \rightarrow 0$），它会变成 $0$；
• $a_4 = 49$，对其进行 $15$ 次操作2，它会变成 $0$。

数据规模与约定

• 对于 $20\%$ 的数据，$n \le 16, a_i \lt 16$
• 对于 $50\%$ 的数据，$n \le 1024, a_i \lt 1024$
• 对于 $100\%$ 的数据，$1 \le n \le 32768, 0 \le a_i \lt 32768$