Дано число \(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\).
Выходные данные
Для каждого набора входных данных в отдельной строке выведите целое число \(m\) — минимальное количество ходов, которые нужно совершить, чтобы число стало степенью \(2\).
Примечание
Ответ на первый набор входных данных разобран выше.
Ответ на второй набор входных данных разобран выше.
В третьем наборе входных данных достаточно приписать справа цифру \(4\) — число \(6\) превратится в \(64\).
В четвёртом наборе входных данных можно сначала приписать справа \(8\), затем удалить \(7\) и \(5\) — получится число \(8\).
В пятом и шестом наборах входных данных числа уже являются степенями двойки, поэтому ни одного хода делать не нужно.
В седьмом наборе данных можно сначала удалить цифру \(3\) (останется \(01\)), затем удалить цифру \(0\) (получится \(1\)).