There are $N$ coins in a row. Each coin is placed showing heads or tails.

You can repeat the following operation any number of times:

• Select two adjacent coins that show the same face, and flip both of them.

Flipping a coin showing heads makes it show tails, and flipping a coin showing tails makes it show heads.

Given the state of each coin, determine whether it is possible to make all coins show heads, and if possible, find the minimum number of operations required.

Input

The first line contains the number of test cases $T$. ($1 \le T \le 10\,000$)

The first line of each test case contains the number of coins $N$. ($1 \le N \le 1\,000\,000$)

The second line of each test case contains a string $S$ of length $N$ representing the state of each coin. For every $1 \leq i \leq N$, the $i$-th character of $S$ is H if the $i$-th coin shows heads, or T if it shows tails.

The sum of $N$ over all test cases does not exceed $1\,000\,000$.

Output

For each test case, output the minimum number of operations needed to make all coins show heads from the given state on a single line. If it is impossible, output $-1$ instead.

Examples

Input 1

2
5
HTHHT
2
HT

Output 1

3
-1