В городе Санкт-Петербург день длится \(2^{100}\) минут. С главной станции города Санкт-Петербург поезда отъезжают в моменты времени \(1\) минута, \(4\) минуты, \(16\) минут и т. д., то есть в моменты времени \(4^k\) для целых \(k \geq 0\). Team BowWow прибыли на станцию в момент времени \(s\) и хотят понять, сколько поездов они уже пропустили, то есть сколько поездов отъехало со станции строго раньше, чем в момент времени \(s\). Например, если \(s = 20\), то они пропустили поезда, отъехавшие в моменты времени \(1\), \(4\) и \(16\). Так как время знаете только вы, подскажите им!
Обратите внимание, что число \(s\) будет дано вам в двоичной системе счисления без ведущих нулей.
Выходные данные
Выведите одно число — количество поездов, отправившихся со станции строго раньше, чем в момент времени \(s\).
Примечание
В первом примере \(100000000_2 = 256_{10}\), пропущенные поезда отъехали в моменты времени \(1\), \(4\), \(16\), \(64\).
Во втором примере \(101_2 = 5_{10}\), поезда отъезжали в моменты времени \(1\) и \(4\).
Третий пример был разобран в условии.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
100000000
|
4
|
|
2
|
101
|
2
|
|
3
|
10100
|
3
|