308703: CF1560D. Make a Power of Two
Memory Limit:256 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Make a Power of Two
题意翻译
给定一个整数 $n$。每次操作你可以做两件事情中的一件: - 删去这个数中的一个数位(如果这个数只剩下一位,则**可以把它删空**)。 - 在这个数的**右边**添加一个数位。 你可以以任意顺序执行无限次操作。但请注意,在删去一个数位之后,这个数可能**包含前导零**(例如在删去 $301$ 中的 $3$ 这一位之后,这个数就会变成 $01$ 而不是 $1$)。 你需要执行若干次操作,使得这个数最终变成一个 $2$ 的次幂,或者说存在一个非负整数 $k$ 使得这个数最终是 $2^k$。最终答案**不能包含前导零**。请求出需要执行的操作的最小次数。 $t$ 组数据,$1\leqslant t\leqslant 10^4$,$1\leqslant n\leqslant 10^9$。题目描述
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 $ .输入输出格式
输入格式
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 $ ).
输出格式
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 $ .
输入输出样例
输入样例 #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