32034번 - 동전 쌍 뒤집기

문제

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

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

• 서로 이웃하면서 같은 면으로 놓여있는 두 개의 동전을 선택하여 둘 다 뒤집는다.

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

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

입력

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

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

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

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

출력

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

제한

힌트