#477 Binary String Reduction

Statement

Statement language

You are given a binary string $S$ of length $N$ consisting only of 0 and 1. The first character of $S$ is always 0.

You may perform the following operation any number of times.

Choose a contiguous substring of the current string whose length is at least $3$ .
Inside the chosen substring, the number of 1s must be exactly one greater than the number of 0s.
Choose one 1 inside the chosen substring and change it to 0.

Among all strings obtainable after performing the operation zero or more times, find the minimum possible number of 1s.

The input is given from Standard Input in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

For each test case, print one line containing the minimum possible number of 1s in an obtainable string.

#	Score	Constraints
1	15	$N \le 8$ . The sum of $N$ over all test cases does not exceed $2\,000$ .
2	25	$N \le 100$ .

Input

Output

The first test case initially contains no 1.

In the second test case, the whole string 011 can be chosen and one 1 can be changed to 0.

In the third and fourth test cases, it is impossible to obtain a string with fewer 1s than the printed value.