$N$ monedas están colocadas en una fila. Cada moneda muestra cara o cruz.

Puedes repetir la siguiente operación tantas veces como desees:

• Elige dos monedas adyacentes que estén mostrando la misma cara y voltéalas ambas.

Voltear una moneda que muestra cara la deja mostrando cruz, y voltear una moneda que muestra cruz la deja mostrando cara.

Dado el estado de cada moneda, determina si es posible hacer que todas las monedas muestren cara y, de ser posible, encuentra el número mínimo de operaciones necesarias para lograrlo.

Entrada

La primera línea contiene el número de casos de prueba $T$. ($1 \le T \le 10\,000$)

La primera línea de cada caso de prueba contiene el número de monedas $N$. ($1 \le N \le 1\,000\,000$)

La segunda línea de cada caso de prueba contiene una cadena $S$ de longitud $N$ que representa el estado de cada moneda. Para todo $1 \leq i \leq N$, el $i$-ésimo carácter de $S$ es H si la $i$-ésima moneda muestra cara, y T si muestra cruz.

La suma total de $N$ sobre todos los casos de prueba no supera $1\,000\,000$.

Salida

Para cada caso de prueba, imprime en una línea el número mínimo de operaciones necesarias para hacer que todas las monedas muestren cara desde el estado dado. Si es imposible, imprime $-1$ en su lugar.

Ejemplos

Entrada 1

2
5
HTHHT
2
HT

Salida 1

3
-1