CF1560D.Make a Power of Two

You are given an integer $n$. In $1$ move, you can do one of the following actions:

• erase any digit of the number (it's acceptable that the number before the operation has exactly one digit and after the operation, it is "empty");
• add one digit to the right.

The actions may be performed in any order any number of times.

Note that if, after deleting some digit from a number, it will contain leading zeroes, they will not be deleted. E.g. if you delete from the number $301$ the digit $3$, the result is the number $01$ (not $1$).

You need to perform the minimum number of actions to make the number any power of $2$ (i.e. there's an integer $k$ ($k \ge 0$) such that the resulting number is equal to $2^k$). The resulting number must not have leading zeroes.

E.g. consider $n=1052$. The answer is equal to $2$. First, let's add to the right one digit $4$ (the result will be $10524$). Then let's erase the digit $5$, so the result will be $1024$ which is a power of $2$.

E.g. consider $n=8888$. The answer is equal to $3$. Let's erase any of the digits $8$ three times. The result will be $8$ which is a power of $2$.

给你一个整数 $n$。在一次操作中，你可以执行以下任意一种操作：

• 删除该数字的任意一位（允许操作前数字仅有一位，且操作后数字“为空”）；
• 在数字右侧添加一位数字。

上述操作可以以任意顺序执行任意多次。

注意：如果从某个数字中删除某一位后，结果包含前导零，则这些前导零不会被自动删除。例如，若从数字 $301$ 中删除数字 $3$，结果为数字 $01$（而非 $1$）。

你需要执行最少次数的操作，使得最终得到的数字是某个 $2$ 的幂（即存在整数 $k$（$k \ge 0$），使得最终数字等于 $2^k$）。最终数字不得包含前导零。

例如，考虑 $n=1052$。答案为 $2$。首先，在右侧添加一位数字 $4$（结果为 $10524$）；然后删除数字 $5$，结果为 $1024$，这是一个 $2$ 的幂。

再例如，考虑 $n=8888$。答案为 $3$。连续三次删除任意一个数字 $8$，结果为 $8$，这是一个 $2$ 的幂。

The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then $t$ test cases follow.

Each test case consists of one line containing one integer $n$ ($1 \le n \le 10^9$).

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。随后是 $t$ 个测试用例。

每个测试用例由一行组成，其中包含一个整数 $n$（$1 \le n \le 10^9$）。

For each test case, output in a separate line one integer $m$ — the minimum number of moves to transform the number into any power of $2$.

对于每个测试用例，在单独一行中输出一个整数 $m$ —— 将该数变为任意一个 $2$ 的幂所需的最少操作次数。

The answer for the first test case was considered above.

The answer for the second test case was considered above.

In the third test case, it's enough to add to the right the digit $4$ — the number $6$ will turn into $64$.

In the fourth test case, let's add to the right the digit $8$ and then erase $7$ and $5$ — the taken number will turn into $8$.

The numbers of the fifth and the sixth test cases are already powers of two so there's no need to make any move.

In the seventh test case, you can delete first of all the digit $3$ (the result is $01$) and then the digit $0$ (the result is $1$).

第一个测试用例的答案已在上文讨论。

第二个测试用例的答案已在上文讨论。

在第三个测试用例中，只需在右侧添加数字 $4$ —— 数字 $6$ 将变为 $64$。

在第四个测试用例中，我们先在右侧添加数字 $8$，然后删除 $7$ 和 $5$ —— 所得数字将变为 $8$。

第五和第六个测试用例中的数字本身已是 2 的幂，因此无需进行任何操作。

在第七个测试用例中，你可以首先删除数字 $3$（结果为 $01$），然后再删除数字 $0$（结果为 $1$）。