$N$ pièces sont alignées. Chaque pièce montre soit face, soit pile.

Vous pouvez répéter l'opération suivante autant de fois que vous le souhaitez :

• Choisir deux pièces adjacentes qui montrent la même face et les retourner toutes les deux.

Retourner une pièce qui montre face la fait montrer pile, et retourner une pièce qui montre pile la fait montrer face.

Étant donné l'état de chaque pièce, déterminer s'il est possible de faire en sorte que toutes les pièces montrent face. Si c'est possible, trouver le nombre minimal d'opérations nécessaire.

Entrée

La première ligne contient le nombre de cas de test $T$. ($1 \le T \le 10\,000$)

La première ligne de chaque cas de test contient le nombre de pièces $N$. ($1 \le N \le 1\,000\,000$)

La deuxième ligne de chaque cas de test contient une chaîne $S$ de longueur $N$ représentant l'état de chaque pièce. Pour tout $1 \leq i \leq N$, le $i$-ème caractère de $S$ est H si la $i$-ème pièce montre face, et T si elle montre pile.

La somme des $N$ sur tous les cas de test ne dépasse pas $1\,000\,000$.

Sortie

Pour chaque cas de test, afficher sur une ligne le nombre minimal d'opérations nécessaire pour que toutes les pièces montrent face à partir de l'état donné. Si c'est impossible, afficher $-1$ à la place.

Exemples

Entrée 1

2
5
HTHHT
2
HT

Sortie 1

3
-1