Switch Array | cho.sh

Problem

A new locking device has been built.

The device consists of switches $s_1, s_2, \ldots, s_N$ , each of which is either open or closed. The state of a switch is 0 or 1, so the state of the device is an array of $N$ bits.

The table below shows an example array with 8 switches.

switch	$s_1$	$s_2$	$s_3$	$s_4$	$s_5$	$s_6$	$s_7$	$s_8$
state	0	1	1	0	1	1	0	0

In an array of $N$ switches, the rules for operating a switch are as follows.

Rule 1) You can toggle $s_N$ at any time to change its state.
Rule 2) When $s_{i+1}$ is 1 and $s_{i+2}, s_{i+3}, \ldots, s_{N-1}, s_N$ are all 0, you can toggle $s_i$ to change its state. This rule also applies when the switches $s_{i+2}, s_{i+3}, \ldots, s_{N-1}, s_N$ do not exist at all. For example, you can toggle $s_{N-1}$ as long as $s_N$ is 1.
Rule 3) You can toggle only one switch at a time.

The device opens when every switch is 0.

Following the rules above, find the minimum number of toggles that turns the given array into all zeros.

The table below is a shortest sequence that turns the array 1111 into 0000. The array 1111 needs at least 10 toggles.

toggles	$s_1$	$s_2$	$s_3$	$s_4$
0	1	1	1	1
1	1	1	0	1
2	1	1	0	0
3	0	1	0	0
4	0	1	0	1
5	0	1	1	1
6	0	1	1	0
7	0	0	1	0
8	0	0	1	1
9	0	0	0	1
10	0	0	0	0

Input

The first line contains the number of test cases $T$ .

Each test case follows on its own line as a bit string $B$ . The first bit of $B$ is $s_1$ and the last bit is $s_N$ .

The length of $B$ satisfies $2 \le |B| \le 31$ .

Output

For each test case, print on one line the minimum number of toggles needed to turn every switch to 0.