Valentine's day is over. But the Bajrang Dal is still active.
Orlando and Rosalind have taken leave from their company HIREDIVE for spending some quality time together.
They are on the base level of a temple with 2^1000 stairs. The base level is represented as 1. Seeing the couple together, the Bajrang Dal members charge towards them. The Bajrang Dal members have a superpower of going from stair number n to the stair which is equal to the number of 1's in the binary representation of n in one operation. For example, if the Bajrang Dal member is at stair number 6 (binary representation 110) it can go to stair number 2 in one operation as the no. of 1's in binary representation of 6 is 2.

You, as an advocate of love are going to help the couple.

You are given the stair number (in binary form) in which the Bajrang Dal members initially are and you need to inform them the number of operations in which the members can reach level 1 (place where Rosalind and Orlando are standing).

Input

The first line contains a single integer t denoting the number of test cases.
Each of the following t lines contains a string denoting the binary equivalent of the stair in which the Bajrang Dal members are present initially.

Output

For each test case, output in a new line the number of operations in which the members can reach level 1.

Constraints

1<=t<=10^5
Binary equivalent string of n where, 1<=n<=2^1000.