题目描述

有 $N$ 枚硬币排成一列。每枚硬币均以正面或反面朝上的状态放置。

你可以执行任意次以下操作：

• 选择两枚相邻且朝上的面相同的硬币，将这两枚硬币同时翻面。

翻转一枚正面朝上的硬币后，它会变为反面朝上；翻转一枚反面朝上的硬币后，它会变为正面朝上。

给定每枚硬币的初始状态，请判断能否使所有硬币最终都正面朝上。若可以，请求出所需操作次数的最小值。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量。

对于每个测试用例：

• 第一行包含一个整数 $N$，表示硬币的数量；
• 第二行包含一个长度为 $N$ 的字符串 $S$，表示每枚硬币的初始状态。

对于每个 $1\le i\le N$：

• 若 $S_i=\texttt{H}$，则第 $i$ 枚硬币正面朝上；
• 若 $S_i=\texttt{T}$，则第 $i$ 枚硬币反面朝上。

输出格式

对于每个测试用例，输出一行：

• 若能够使所有硬币正面朝上，输出所需操作次数的最小值；
• 若无法做到，输出 -1。

数据范围

• $1\le T\le 10\,000$；
• $1\le N\le 1\,000\,000$；
• 所有测试用例的 $N$ 之和不超过 $1\,000\,000$。

样例输入

2
5
HTHHT
2
HT

样例输出

3
-1