Making a Good Binary String

A binary string $a\_1a\_2...a\_n$ of length $n$ made of $0$ and $1$ is given. For a cost of $1$, you can change one character into the other character.

A good binary string is a string that satisfies all of the following conditions.

• It contains at least one $0$ and at least one $1$.
• The minimum length of an interval containing all $0$s is equal to the minimum length of an interval containing all $1$s. An interval [$s$, $e$] contains $j$ if every $i$ with $a_i=j$ satisfies $s \leq i \leq e$ ($1 \leq i \leq n$, $j=0$, $1$). The length of an interval [$s$, $e$] is defined as $e-s$.

Find the minimum cost to turn the given string into a good binary string.

The first line contains the number of test cases $T$ ($1 \leq T \leq 10^3$).

Each test case consists of the following.

The first line contains the length of the binary string $n$ ($1 \leq n \leq 10^6$).

The next line contains a string of length $n$ made of $0$ and $1$.

It is guaranteed that the sum of $n$ over all test cases is at most $10^6$.

For each test case, print $-1$ if the given string cannot be turned into a good binary string. Otherwise, print the minimum cost to turn it into a good binary string.