J. 동전 쌍 뒤집기
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

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

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

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

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

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

Input

첫 줄에 테스트 케이스의 개수 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을 넘지 않는다.

Output

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

Example
Input
2
5
HTHHT
2
HT
Output
3
-1