有 $N$ 枚硬币排成一行。每枚硬币显示为正面或反面。

你可以进行任意多次以下操作：

• 选择两个相邻且面相同的硬币，将它们都翻转。

翻转一枚正面的硬币会得到反面，翻转一枚反面的硬币会得到正面。

给定每枚硬币的状态，判断是否可以通过操作使所有硬币都变为正面，如果可以，求出所需的最少操作次数。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量。（$1 \le T \le 10\,000$）

每个测试用例的第一行包含一个整数 $N$，表示硬币的数量。（$1 \le N \le 1\,000\,000$）

每个测试用例的第二行包含一个长度为 $N$ 的字符串 $S$，表示每枚硬币的状态。对于所有 $1 \leq i \leq N$，$S$ 的第 $i$ 个字符若为 H 则表示第 $i$ 枚硬币为正面，若为 T 则表示反面。

所有测试用例的 $N$ 之和不超过 $1\,000\,000$。

输出格式

对于每个测试用例，输出一行，表示使所有硬币变为正面所需的最少操作次数。如果不可能，则输出 $-1$。

样例

输入 1

2
5
HTHHT
2
HT

输出 1

3
-1