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

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

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

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

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

Input

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

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

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

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

Output

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

Examples

Input 1

2
5
HTHHT
2
HT

Output 1

3
-1