Switch Array

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.

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.

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$.

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