该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

对于一个整数$v$，有两种操作，分别是：

• 令$v=(v+1) \bmod 32768$
• 令$v=(2 \cdot v) \bmod 32768$

给出$n$个整数$a_1, a_2, \ldots, a_n$，对于每一个$a_i$，至少要经过多少次操作才能令$a_i$变成0？

输入格式

第一行给出$n(1 \leq n \leq 32768)$表示查询个数。

第二行包括$n$个整数$a_1, a_2, \ldots, a_n(0 \leq a_i < 32768)$。

输出格式

输出$n$个整数，第$i$个整数表示至少要经过多少次操作，才能令$a_i$等于0。

样例

输入：

4
19 32764 10240 49
    

输出：

14 4 4 15
    

数据范围与提示：

• 让我们考虑每个 $a_i$：
• $a_1=19$。你可以首先将其增加1得到20，然后将其乘以2共13次。你将在1+13=14步内得到0。
• $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次。

样例