$N$ 個のコインが一列に並んでいる。各コインは表または裏が上になるように置かれている。

あなたは次の操作を好きなだけ繰り返すことができる。

• 隣り合っていて同じ面が上になっている 2 枚のコインを選び、両方をひっくり返す。

表が上になっているコインをひっくり返すと裏になり、裏が上になっているコインをひっくり返すと表になる。

各コインの状態が与えられたとき、すべてのコインを表が上になるようにできるか判定し、可能ならばそのために必要な操作の最小回数を求めよ。

入力

最初の行にテストケースの個数 $T$ が与えられる。($1 \le T \le 10\,000$)

テストケースの最初の行にはコインの枚数 $N$ が与えられる。($1 \le N \le 1\,000\,000$)

テストケースの 2 行目には、各コインの状態を表す長さ $N$ の文字列 $S$ が与えられる。すべての $1 \leq i \leq N$ について、$S$ の $i$ 番目の文字は、$i$ 番目のコインが表の場合は H、裏の場合は T である。

すべてのテストケースに対する $N$ の合計は $1\,000\,000$ を超えない。

出力

各テストケースについて、与えられた状態からすべてのコインを表が上になるようにするために必要な操作の最小回数を一行に出力する。不可能な場合は $-1$ を代わりに出力する。

入出力例

入力 1

2
5
HTHHT
2
HT

出力 1

3
-1