D. Сделай степень двойки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано число $$$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$$$. В результате получится $$$8$$$, что является степенью числа $$$2$$$.

Входные данные

В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следуют $$$t$$$ наборов входных данных.

Каждый набор входных данных состоит из одной строки, содержащей одно целое число $$$n$$$ ($$$1 \le n \le 10^9$$$).

Выходные данные

Для каждого набора входных данных в отдельной строке выведите целое число $$$m$$$ — минимальное количество ходов, которые нужно совершить, чтобы число стало степенью $$$2$$$.

Пример
Входные данные
12
1052
8888
6
75
128
1
301
12048
1504
6656
1000000000
687194767
Выходные данные
2
3
1
3
0
0
2
1
3
4
9
2
Примечание

Ответ на первый набор входных данных разобран выше.

Ответ на второй набор входных данных разобран выше.

В третьем наборе входных данных достаточно приписать справа цифру $$$4$$$ — число $$$6$$$ превратится в $$$64$$$.

В четвёртом наборе входных данных можно сначала приписать справа $$$8$$$, затем удалить $$$7$$$ и $$$5$$$ — получится число $$$8$$$.

В пятом и шестом наборах входных данных числа уже являются степенями двойки, поэтому ни одного хода делать не нужно.

В седьмом наборе данных можно сначала удалить цифру $$$3$$$ (останется $$$01$$$), затем удалить цифру $$$0$$$ (получится $$$1$$$).