동전 쌍 뒤집기

$N$개의 동전이 일렬로 놓여 있다. 각 동전은 앞면이나 뒷면이 보이도록 놓여 있다.

다음 조작을 원하는 만큼 반복할 수 있다.

• 서로 이웃하면서 같은 면이 보이는 동전 두 개를 선택하여 둘 다 뒤집는다.

앞면이 보이는 동전을 뒤집으면 뒷면이, 뒷면이 보이는 동전을 뒤집으면 앞면이 보이게 된다.

각 동전의 상태가 주어졌을 때 모든 동전을 앞면이 보이도록 놓을 수 있는지 판단한다. 가능하다면 그렇게 하는 데 필요한 조작의 최소 횟수를 구한다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. ($1 \le T \le 10\,000$)

각 테스트 케이스의 첫 줄에는 동전의 개수 $N$이 주어진다. ($1 \le N \le 1\,000\,000$)

각 테스트 케이스의 둘째 줄에는 동전의 상태를 나타내는 길이 $N$의 문자열 $S$가 주어진다. 모든 $1 \le i \le N$에 대해 $S$의 $i$번째 문자는 $i$번째 동전이 앞면이면 H, 뒷면이면 T이다.

모든 테스트 케이스에 대한 $N$의 총합은 $1\,000\,000$을 넘지 않는다.

각 테스트 케이스에 대해, 주어진 상태에서 모든 동전을 앞면이 보이도록 하는 데 필요한 조작의 최소 횟수를 한 줄에 출력한다. 불가능하면 $-1$을 출력한다.