시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)386877925.733%

문제

$0$과 $1$로 이루어진 길이 $n$의 이진 문자열 $a_1a_2...a_n$이 주어진다. 여러분은 비용 $1$로 하나의 문자를 다른 문자로 바꿀 수 있다.

좋은 이진 문자열은 다음을 만족하는 문자열이다.

  • $0$과 $1$을 적어도 하나씩 포함한다.
  • $0$을 포함하는 구간의 최소 길이는 $1$을 포함하는 구간의 최소 길이와 같다. 구간 [$s$, $e$]가 $j$를 포함한다는 것은 $a_i=j$인 모든 $i$에 대해 $s \leq i \leq e$가 성립한다는 것이다. ($1 \leq i \leq n$, $j=0$, $1$) 구간 [$s$, $e$]의 길이는 $e-s$로 정의한다.

주어진 문자열을 좋은 이진 문자열로 만드는 데 필요한 최소 비용을 구하시오.

입력

첫째 줄에는 테스트케이스의 개수 $T$가 주어진다. ($1 \leq T \leq 10^3$)

각 테스트케이스는 다음과 같은 구성을 가진다.

첫째 줄에는 이진 문자열의 길이 $n$이 주어진다. ($1 \leq n \leq 10^6$)

다음 줄에는 $0$과 $1$로 이루어진 길이 $n$의 문자열이 주어진다.

모든 테스트케이스에 대해서 $n$의 합이 $10^6$ 이하임이 보장된다.

출력

각 테스트 케이스에 대해서 주어진 문자열을 좋은 이진 문자열로 만들 수 없다면 $-1$을 출력한다. 좋은 이진 문자열로 만들 수 있다면 좋은 이진 문자열로 만들기 위한 최소 비용을 출력한다.

예제 입력 1

3
6
100100
5
10010
1
0

예제 출력 1

1
0
-1

첫 번째 테스트케이스의 경우, $5$번째 문자를 $1$로 바꾸면 문자열이 $100110$이 된다.

[$1$, $5$]는 $1$을 포함하며 이는 $1$을 포함하는 구간 중 최소 길이를 가지는 구간이다.

[$2$, $6$]는 $0$을 포함하며 이는 $0$을 포함하는 구간 중 최소 길이를 가지는 구간이다.

두 구간 모두 길이가 $4$이기 때문에 새로 만든 문자열은 좋은 이진 문자열이다.

비용 $0$으로는 좋은 문자열을 만들 수 없다.

두 번째 테스트케이스의 경우 문자열이 이미 좋은 문자열이기 때문에 답은 $0$이다.

세 번째 테스트케이스의 경우 길이 $1$의 문자열은 $1$과 $0$을 둘 다 포함할 수 없기 때문에 주어진 문자열을 좋은 문자열로 만들 수 없다.