#477 Binary String Reduction

Statement

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

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

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

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

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

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

$N$ $S$

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

Input

Output

첫 번째 테스트 케이스에는 처음부터 1이 없다.

두 번째 테스트 케이스에서는 전체 문자열 011을 골라 1 하나를 0으로 바꿀 수 있다.

세 번째와 네 번째 테스트 케이스에서는 출력된 개수보다 더 적은 수의 1을 만들 수 없다.