좋은 문자열 만들기

$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$을 출력한다. 만들 수 있으면 좋은 이진 문자열로 만들기 위한 최소 비용을 출력한다.