$N$ monet jest ułożonych w rzędzie. Każda moneta jest ułożona tak, aby widoczny był orzeł lub reszka.

Możesz wielokrotnie wykonywać następującą operację:

• Wybierz dwie sąsiednie monety, które leżą tą samą stroną do góry, i odwróć obie.

Odwrócenie monety z orłem daje reszkę, a odwrócenie monety z reszką daje orła.

Mając dany stan każdej monety, sprawdź, czy możliwe jest ułożenie wszystkich monet tak, aby pokazywały orła, a jeśli tak, znajdź minimalną liczbę operacji potrzebną do osiągnięcia tego celu.

Wejście

W pierwszym wierszu podana jest liczba zestawów danych $T$ ($1 \le T \le 10\,000$).

W pierwszym wierszu każdego zestawu danych podana jest liczba monet $N$ ($1 \le N \le 1\,000\,000$).

W drugim wierszu każdego zestawu danych podany jest ciąg znaków $S$ o długości $N$ reprezentujący stan monet. Dla każdego $1 \leq i \leq N$, $i$-ty znak $S$ to H, jeśli $i$-ta moneta pokazuje orła, lub T, jeśli pokazuje reszkę.

Suma wartości $N$ po wszystkich zestawach danych nie przekracza $1\,000\,000$.

Wyjście

Dla każdego zestawu danych wypisz w osobnym wierszu minimalną liczbę operacji potrzebną do tego, aby wszystkie monety pokazywały orła. Jeśli jest to niemożliwe, zamiast tego wypisz $-1$.

Przykład

Wejście 1

2
5
HTHHT
2
HT

Wyjście 1

3
-1