Yet Another Binary Problem 2

0과 1로만 이루어진 길이 $N$의 이진 문자열 $S$가 주어진다. $S$의 첫 번째 문자는 항상 0이다.

다음 연산을 원하는 만큼 수행할 수 있다.

• 현재 문자열에서 길이가 $3$ 이상인 연속 부분 구간을 하나 고른다.
• 고른 구간 안의 1의 개수가 0의 개수보다 정확히 $1$ 많아야 한다.
• 고른 구간 안의 1 중 하나를 골라 0으로 바꾼다.

연산을 $0$번 이상 수행하여 얻을 수 있는 모든 문자열 중, 1의 개수의 최솟값을 구하여라.

입력은 다음과 같은 형식으로 주어진다.

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

각 케이스는 다음과 같은 형식으로 주어진다.

$N$ $S$

각 테스트 케이스마다 한 줄에, 만들 수 있는 문자열의 1의 개수의 최솟값을 출력한다.

• $1 \le T \le 2\,000$.
• $1 \le N \le 2\,000$.
• $|S|=N$.
• $S_i$는 0 또는 1이다 ($1 \le i \le N$).
• $S_1=\texttt{0}$.
• 모든 테스트 케이스에 대한 $N$의 제곱합은 $4\,000\,000$ 이하이다.