Binary String Reduction

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$ $\vdots$ $\mathrm{case}_T$

Each case is given in the following format:

$N$ $S$

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

• $1 \le T \le 2\,000$.
• $1 \le N \le 2\,000$.
• $|S|=N$.
• $S_i$ is either 0 or 1 ($1 \le i \le N$).
• $S_1=`0`$.
• The sum of $N^2$ over all test cases does not exceed $4\,000\,000$.