Hector Barbossa and his mutinuous crew stole the Black Pearl ship from Captain Jack Sparrow and went on to loot the 882 identical pieces of Aztec Gold from the chest delivered to Cortez. They had to pay a horrible price as the gold was cursed. Food turned to ashes in their mouth and wine could not quench their thirst.
There was only one way to release the curse. They have to return every single piece of gold that they had stolen and repay the blood. Every piece of gold has a binary number written on it. In order to place a piece back in the chest, the binary number on it has to be reduced to the number "1". The pirates can divide the number by 2 if it is even and add 1 to the number if it is odd. Each of this operation takes 1 minute.
The pirates are eager to release their curse but they are weak in mathematics. Help them find the minimum time required to return each piece of gold to the chest.
Input
Each file contains 882 lines. Each line contains a binary number.
Output
Output the minimum time required to return each piece of gold to the chest in a new line.
Constraints
1 <= No. of digits in the binary number <= 32800
The first digit of every number will be 1
NOTE
The time limit of 1 sec is for all test files combined.
There are total 6 test files.
Use faster I/O techniques like scanf
Do not try to use the "Compile and Test" button for this question.
3rd test case : Number 101110 is even, which means that we should divide it by 2. After the division pirates gets an odd number 10111 and adds one to it. Number 11000 can be divided by 2 three times in a row to get number 11. All that's left is to increase the number by one (we get 100), and then divide it by 2 twice. As a result, we get 1. Hence 8 minutes are required.
