$N$ монет выложены в ряд. Каждая монета лежит орлом или решкой вверх.

Вы можете повторять следующую операцию любое количество раз:

• Выбрать две соседние монеты, лежащие одной и той же стороной вверх, и перевернуть обе.

При перевороте монеты, лежащей орлом вверх, она становится решкой, а при перевороте монеты, лежащей решкой вверх, она становится орлом.

По заданному состоянию каждой монеты определите, можно ли перевернуть все монеты орлом вверх, и если да, найдите минимальное количество операций, необходимых для этого.

Входные данные

Первая строка содержит количество тестов $T$ ($1 \le T \le 10\,000$).

Первая строка каждого теста содержит количество монет $N$ ($1 \le N \le 1\,000\,000$).

Вторая строка каждого теста содержит строку $S$ длины $N$, описывающую состояние монет. Для всех $1 \le i \le N$ $i$-й символ $S$ равен H, если $i$-я монета лежит орлом вверх, и T, если решкой.

Сумма $N$ по всем тестам не превышает $1\,000\,000$.

Выходные данные

Для каждого теста выведите в отдельной строке минимальное количество операций, необходимое, чтобы все монеты оказались орлом вверх. Если это невозможно, выведите $-1$.

Примеры

Входные данные 1

2
5
HTHHT
2
HT

Выходные данные 1

3
-1