P20030 [HackerEarth] 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.
普及
题目描述

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.

SAMPLE INPUT
1
1001001
101110
.
.
.
879 other lines

SAMPLE OUTPUT
0
12
8
.
.
.
879 other answers

Explanation

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.

输入格式

见题面

输出格式

见题面

样例输入
1110110110111101 11101110011011 11110010 101101 11011011 11001010010111001 1110010110 10011011010 111011010000 1110010010110101 10101 1101011011011110 1111100 10000100110 11011100101111110000 10101011011110110 1110 11110011000110101 1100000 11 11001 1000011 1111100100011 10 110010111010010 11110100010010110111 11011110111001101 101100011001011 110 1011 11011010011000001010 1111 100 111 11111 11111110010001100 10 111 11110101 10 111011 11111011010010011001 11 11100010 101111 1110001 1100101100110 11000100 100111100100 1101011110111 1000011 11100000011010 11100001101111011 11011010010100000001 11000100100001100101 11100101111000100000 1001101010000101101 10100001100101001 10000111011001010100 110001111001111011 1110 1010100110100011 1010001101001111 10000001111 10100 11 110110101011010011 1111010100001101 11001001110 10010100111011101011 111110011011101001 110 110110011000001 10101 110 1010100101010000101 1010010 111100011011110 11101111111100 111 1000001001 110 101100010111100111 1100100 1 11 1010111110101101 1010111000100001 100101101 111 11001110010010 101 11111101101 10001110101000101001 110 10100110000001101 1111110101 1 10101 111000 100001000000111001 11011000011110 1011 10000 11101 10101100010001 10101101100011101 101 11011000011100 1000011010010101110 110011111000110 10 10011101001100 10100000110000001000 1111010101 10000100110000 1100100101011011 10 11111110001000101001 110101111011111010 110 1111100001100101 10110110010 110 11110011001 10 111010110110011 11100101100 1 111011 11010 1001110 1101001 1 111001000 1111111011000 111010100111101110 10011101010 1001100000 10111000100 1100 1000000101001100110 101101 110100101110111 1011000100110111111 1010111 10101 111 11 1110 110111100111001000 110110100 110001000 111011000110 10011101101000010101 10010011 10000111100010110 10111101111010 11111010 101100011 1 10 11010111110110011100 100000 101011000 1010100111110110 1011100010000 1 1000110110000 10001 1111 100010000011111010 101100000111000011 1111011110 11010010 10000 1111000 10011111100101001110 1111100 10110010111 110001001110001 1011 1100 110000111110100 1000101010011011 1010101101100 10 1111100100100101 1010 10100101100 11000001010000 1100010001010000 1000001 10010111111000 10011001010010111 11011011 1011010100 1 11111100100110 10010111011011101111 100101 110 10000 1001111110010 10001011 101010110001100 1 100111000111000 110101 1000 101111 11 10001111100 110101011111 1001000110111100 11111011010000 11000111101010011 10110101100110011100 10101100101000001 11001110010100101 110000010000 11111100000111100 111111 10100110101110010011 1110100011 1 1100011100 10 1010000111 100 10010010110 1001001011000000 11 101001 1100000101010 110011011111001100 1001 10100001101 11011 11000001111 1001110111001 10101101000010 1100001101101101001 1 101011 1 101011100010001 111110110000 1110101110001100 10101100 111110111000 110101001100001 101110 11100 101010111001111111 11011110100101 1110111011100111 11001001 111110101110110000 10 111101 11000000 1 11011001001001100011 100000100111100 100110101 10010011111011110101 111000 10 11010011001 10001100000111011101 111000001 10011010101101000 11011110011 100 110001000001110 1011111011 10101100 11100 11111 10110000011110 101001101011010 1101 101101011 111001100110011110 111001110001 11001110001 11001000000010101000 10101001010101011 1000101000100011010 1 111001110010011010 101010001101001 11 100111 111 111110 10 110000 10100000 1111110010100100 11111000 1100 111101010101111111 10001 101110111100 1100000110110111000 11101101010110011 1 100 1100 11000011 111011 1 101101110 10 1001110010000 1 10 110010 110 10010100101 10111011101001 1111111 11100011010100 11011100010110010011 110010 10100111010001101 101101010110001 10110100001010 100001 111000101 1110111000000011000 1 10100110111010 100 1010110110 11010000000001 1110111111110 1001101100101000111 111110101 1011000100000101 1101 11010101011010 10001 11000 1011000110001 111000 10000110011110000111 1010 11 1 111 1101011101101111 1111100100 101010001 1111 10010 1110111111011 10101110001011011 110 110100 111110001111101000 100101 111100101101000 111 110001011 1011011101011100011 1 101000101 111100111 11000011111001010 110111111100000011 11000111001011 11 11100000 10 101110 1110 1100001110000 11001111111 11 1001110 11010000 101000100011 1011010001111000001 11001 10 1100 1110000 11001000000 1100101 100010100010 10001111010000 101101100 1101010101110101100 1 10001000 1100100001011 10100010100 1 111101000101 1100 1100 1101101010110001 1001110010110 1011001011010010 11110 1010001 111110010 100110101101011 11011000111 100 1000010100110111010 111111011100011010 111001 10010110110111000 10101110111011000001 11110011000 1010 1 10011000 11010010100011101 110000111100 1 111101 10110101101001111 111 1011011 10110110110000 11111 11000100100000111 11000110000 11100111 101110011111010 10011 1 11100001100000 101011100 100011101111110 11001011011 110001 11011111011 11000001101010100 111101101001 110001011101 10001111001101110001 110010 111110010110 100111110100101 110011100010011110 1000111101001110000 1010001010001 101101 100 1 111001001111110010 10010100000100100100 100010001100101 1 1101000110 10 1000111001110111 11011111100011100 10111111010110011111 10001100100 11101101001011010100 110 1001010001111000110 11101001101010 11000100 1000001110 1100011001011000 10010011001011110 1100 1001 1000010010011 10011101001101 1000010101 10 101110010101001 101010001001 10001110101 11111 10100001101111 100 11110000000 1010000101010010 11000101010011 111110001 10101 1110000 111100110101000 11101 11000010110011110 111100101111 10010001111001000 10 11001 1110 100100011111110 1 110110000111101100 1000000110111010 1110010001011100101 100011011111101 10 1010110001000110000 11 101001000101 101010111 11000110 10101100000111100 11010011111110111010 1001001110100100 110100110000 10001000001 10100010110100110010 11 111111 1001100001011010010 1111011010011011011 1111011 111010111011110000 1000011100010111101 110000110111111 1001 11011000010 11010100 100 10101011001101011 10110001000110000 110101110111000 100 111100100010010110 110111000 1001011 1100001110101100101 1 100 1110111011010 11 11000 10000 1111 101100001011 100100010001101100 10010 1111111101001110010 100 1001101101 1100110011111000000 11110100000 10010 11101 1 111 111011111 1 110010001 1 11100100000 11111110011110000111 110100101 110100010100100100 101000 1011110101001101 111001110 1111000110101 1100110100111100001 111001101000001 1011 11011010000100 110111 11111 1110101001101 1011111111011101110 100110010010010111 10100010100010 110110 10000100 110 10010110111110100 111 10101011110 101111100 11001 10001110011101100 1 10110011001 11 11011 10111 11010010011000 10101010001010111101 100 110 11 11110110111 11101100111001 10110111100000010 1001011101 10 101011010101 1 11001100 101101100100 11111111100 1100111111101101000 10000110 1111111110111001 11011110 1110010111111 1100010110 10000 10101011 1010001110 10010101110 11101001010010 1101110110000 111010001000110 1001 11100011000110001 1111001100000010100 10111110001011011 10111010101010 1111101 100 101011011000110 110110110000000111 101100101111011100 10011010 11 1011111111 1100 11011110010001 111 111101010010 10 1 10101001001100 1110100 1 111011 11100111000 1000 1011010010000100 11011 11 1000 101 1001100101010111 11001 1011 1111001111100100110 10 11100 110110110001011001 1101001100100000 110110101001 110100010101 1110 10010 1010111010000111100 10000000000 1011100 10110011001001101 101111001001 10 1 111 101101011111 1111 10100010010110 1111 100 10101 111 10001111 11011111001 1000 111011000110 111110110111 100001100 101110001010010111 11010 10111011000 111000000 10010000110001000 1111000101111 10101101010010 10100111111100011 1010010100111 1011001 100010001011100101 10010010110001010010 1 1101100101 110100 100011100110001111 10101111001 10100111101011 11100001111110111010 110011100100 110000010111 1111 1111010 1101001 110 110111101101 111001101 101 1111110 1111100110110000 1101011 1101111001100011 1 10010101001110101 10101001100000100 111 1111101001 11100010101001101011 1100110101111111111 100001101101011001 1101011110 10110010110 111001111000110000 1100101 100 111001000 1001011011 11011110010101001 10101011101011110 10101101111111 1001000111 111110100110111 11100010011 11010000011100 1111100001 10101 1100100011 110010000001 1110111111101000 11 1 10000110 11111 1110000001011 11 11110000101011100100 1101001011101000 1 1010100 1101110010110110011 1010101111100 100001100010100 1000110111111 10100 10011000111101 11110111000110 10100110 11100000 1010101 11110011000 100100 1 1011111 101011 10 10001000 10001101 10111110101100011 10101001 101001100 101001101 1110 1101010001 11011111010001001 10001001001000111010 1101011010101 1011001111 111100 11100000 1010101001000011100 100010110101 1 10111110101 11000 11 10101010111100101 1101111100001111 1001000010101 11010110111011101101 11000 101 11011 100011 111001 1 110100 100010011010100010 101 10001000010101 11101110010 100111 10000 1010011101100 1 1011101101011000 10001011011 1010010100000 10100110001 110011110110100001 11110010100000 11101001010 11011 1101101110111100101 11111100 10011010010110 100 1110101100 11001111001 11000111 10100 1111110110110111110 11000100011101 11111010101010 10111011000001011 1110001 11000 1010111111010 1101101 11000101 110011111010000111 1 1 10 1010101111111100 1001111110000 1100100001100101 1001001001000 1011 1001000110101101011 100100 101010011000100 110001001 1000101101100 1 100 111101011101111 10111110100110 11010111010111 1100100111010111101 100101011111010111 11001010101000 10001 11010 11110 10000110000110110 11100010010100101 111010010100 10010111 111001101011001 101101011110001001 11110100010010 11 10101000 110000000111010100 111110 11100 1101001010 101 10010100010110 10000000111 1 1 100111011011111 1011110101110 101100111 11100111100010100001 1010111001100000 110001001000011001
样例输出
104 140 102 101 145 33 81 125 19 11 43 19 8 17 114 12 26 81 56 72 98 11 100 74 95 84 65 35 15 141 45 99 20 57 112 116 26 72 1 45 119 108 149 56 47 148 42 8 44 148 117 105 65 97 143 118 49 17 34 37 121 77 5 139 81 93 71 112 89 70 123 16 122 64 113 89 20 89 117 58 85 51 103 92 36 139 127 104 120 49 69 122 61 64 123 90 146 75 51 30 33 122 140 62 113 9 22 69 16 52 45 139 51 41 8 34 134 86 56 57 155 36 103 147 20 9 27 141 93 85 41 132 10 47 57 50 117 22 134 129 123 127 132 133 21 104 105 50 88 106 49 29 4 35 97 104 31 10 121 140 44 77 38 89 82 16 67 132 49 24 7 145 116 123 69 111 134 63 90 122 128 141 103 158 47 73 131 106 115 51 53 125 0 17 135 50 45 54 113 53 82 35 22 43 140 108 98 65 40 74 100 59 3 107 79 30 74 124 27 1 120 124 24 105 120 84 57 12 32 17 89 72 36 46 130 13 114 148 41 34 81 7 42 155 102 57 146 102 79 11 41 119 114 36 140 62 50 124 10 52 82 146 99 15 93 136 32 136 147 72 59 96 17 31 62 112 144 45 8 48 109 87 49 136 91 130 87 59 28 103 100 32 86 103 21 58 19 64 4 145 24 44 32 5 131 127 72 92 26 47 61 139 116 131 63 16 86 71 5 72 100 12 115 6 97 46 28 126 33 114 108 22 81 111 101 23 77 47 77 8 20 52 138 100 87 71 43 17 125 141 79 55 27 88 114 45 95 99 69 62 23 62 27 44 115 104 24 28 0 31 129 30 135 139 106 71 48 112 144 105 34 134 134 93 64 61 20 12 137 66 48 71 105 97 84 43 92 106 144 72 55 49 146 29 14 65 3 61 2 15 129 50 113 21 101 153 141 119 73 22 84 142 53 36 87 11 98 80 39 130 84 69 7 8 56 110 106 78 15 110 11 110 96 77 94 129 63 37 27 38 95 150 78 131 153 91 28 134 138 53 86 12 138 23 138 133 11 93 145 119 41 85 69 37 21 77 30 62 124 9 40 104 111 151 130 56 95 47 131 99 9 71 26 56 46 94 153 97 22 155 98 135 74 100 22 60 96 38 128 10 116 27 52 155 33 7 117 119 42 82 80 22 0 93 141 21 32 131 0 70 117 122 87 100 31 50 69 120 13 117 72 133 147 23 39 50 90 123 141 44 68 12 1 134 41 42 28 134 12 86 82 6 7 20 32 42 74 69 127 64 8 79 20 54 112 71 68 26 81 35 25 114 73 4 1 153 88 115 25 148 7 20 84 0 83 109 5 66 13 57 114 17 14 45 99 52 40 118 113 134 33 64 101 88 110 75 122 66 149 123 116 111 90 140 24 125 79 51 144 128 143 7 5 57 41 43 70 3 60 19 96 131 85 9 18 137 65 21 59 35 133 101 6 3 86 18 87 87 46 29 59 16 117 42 22 35 126 104 74 124 68 34 45 99 113 115 102 14 93 84 82 153 33 10 101 95 9 15 47 41 78 80 23 66 105 111 7 20 133 138 80 115 62 147 63 109 123 65 132 25 110 14 19 110 72 117 88 129 153 61 134 40 97 48 1 117 5 82 63 114 102 52 35 131 123 53 46 0 61 100 1 128 66 138 130 32 106 32 53 91 31 115 62 130 6 15 127 62 127 10 134 136 58 42 130 6 11 85 0 38 150 48 63 72 1 99 82 40 69 16 59 85 52 6 40 43 31 17 100 146 8 0 141 123 23 58 52 132 148 51 71 1 26 28 87 64 1 60 72 87 53 114 57 49 99 11 113 80 29 45 93 96 114 64 39 9 68 114 121 12 17 0 89 28 92 123 125 103 91 81 0 51 20 143 62 45 111 13 0 43 117 135 13 88 66 29 57 84 65 43 140 20 15 32 28 44 106 30 23 32 53 1 54 51 75 9 66 130 148 92 31 26