Daisy loves math a lot. That's why she plays with numbers when she is bored, and she likes to perform particular operations on these numbers. Daisy takes some positive integer x and, through a series of steps, wants to produce 1 from it. While x is not equal to 1, Daisy repeats the following action: if x is odd, then she adds 1 to it, otherwise she divides x by 2. Daisy knows that for any positive integer this process ends in finite time. How many actions should Daisy perform to get a number one from number x?
Input Format
The first line of input has a single integer, which is the number of test cases T. The next T lines each have a positive integer x in the binary number system. It is guaranteed that the first binary digit of x is non-zero and the number of digits does not exceed 106.
Sample Input
3
1001001
11110001101
11
Output Format The output should consist of T lines, each with a single integer. The ith line should contain the answer for the ith test case.
Sample Output
12
16
3You must be logged in to submit a solution.