← 返回题目列表

Codeforces · 1560/D

D. 求二的幂

中文机器翻译题面 查看原题

给你一个整数$$$n$$$。在 $$$1$$$ 移动中,您可以执行以下操作之一:

- 删除数字的任意一位(可以接受的是,运算前的数字只有一位,运算后为“空”);
- 在右侧添加一位数字。

这些操作可以按任意顺序执行任意次数。

请注意,如果从数字中删除某些数字后,该数字将包含前导零,则它们不会被删除。例如。如果从数字 $$$301$$$ 中删除数字 $$$3$$$,则结果是数字 $$$01$$$(而不是 $$$1$$$)。

您需要执行最少数量的操作才能使数字达到 $$$2$$$ 的任意幂(即存在一个整数 $$$k$$$ ($$$k \ge 0$$$),使得结果数字等于 $$$2^k$$$)。结果数字不得有前导零。

例如考虑 $$$n=1052$$$。答案等于$$$2$$$。首先,我们在右侧添加一位数字$$$4$$$(结果将是$$$10524$$$)。然后我们删除数字$$$5$$$,所以结果将是$$$1024$$$,它是$$$2$$$的幂。

例如考虑$$$n=8888$$$。答案等于$$$3$$$。让我们将 $$$8$$$ 中的任意数字擦除 3 次。结果将是 $$$8$$$,它是 $$$2$$$ 的幂。

输入

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

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

输出

对于每个测试用例,在单独的行中输出一个整数 $$$m$$$ — 将数字转换为 $$$2$$$ 的任意幂的最小移动次数。

示例

输入 #1

12
1052
8888
6
75
128
1
301
12048
1504
6656
1000000000
687194767

输出 #1

2
3
1
3
0
0
2
1
3
4
9
2

注意

第一个测试用例的答案已在上面考虑。

上面考虑了第二个测试用例的答案。

在第三个测试用例中,在右侧添加数字 $$$4$$$ 就足够了 - 数字 $$$6$$$ 将变成 $$$64$$$。

在第四个测试用例中,让我们在右侧添加数字 $$$8$$$,然后删除 $$$7$$$ 和 $$$5$$$ — 得到的数字将变成 $$$8$$$。

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

在第七个测试用例中,您可以首先删除数字$$$3$$$(结果是$$$01$$$),然后删除数字$$$0$$$(结果是$$$1$$$)。