给你一个整数$$$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$$$)。