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.