海狸贝克（Baker Beaver）准备了一个长条形的水果塔。这个塔上装饰着 $2N + 1$ 个配料：$N$ 个靛蓝浆果（Indigo berries）、$N$ 个橘子片（Tangerine slices）以及恰好一个杏仁蛋白软糖星（Marzipan star）。如果配料的排列形式为 $\text{M}\underbrace{\text{ITIT}\dots\text{IT}}_{N \text{ times}}$，海狸贝克就会感到高兴。也就是说，第一个配料应该是 $\text{M}$，随后 $\text{I}$ 和 $\text{T}$ 交替出现，且以 $\text{I}$ 开头。

然而，在早晨的忙乱中，配料被放置成了乱序，由一个长度为 $2N + 1$ 的字符串 $s$ 表示，其中包含字符 $\text{M}$、$\text{I}$ 和 $\text{T}$。为了在不破坏塔皮的情况下修复它，你可以执行任意次数（可能为零）的以下操作：

• 选择一个下标 $i$ ($1 \le i < |s|$)，将字符串拆分为两部分 $s[1 \dots i]$ 和 $s[i + 1 \dots |s|]$，然后交换这两部分，得到新字符串 $s[i + 1 \dots |s|] + s[1 \dots i]$。

求使海狸贝克高兴所需的最少操作次数。如果不可能，输出 $-1$。

输入格式

每个测试包含多个测试用例。第一行包含一个整数 $T$ ($1 \le T \le 10^4$)，表示测试用例的数量。接下来是各测试用例的描述。

每个测试用例的第一行包含一个整数 $N$ ($1 \le N \le 10^5$)。

每个测试用例的第二行包含一个长度为 $2N + 1$ 的字符串 $s$，其中包含 $N$ 个 $\text{I}$，$N$ 个 $\text{T}$，以及恰好一个 $\text{M}$。

所有测试用例的 $N$ 之和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一个整数，表示使海狸贝克高兴所需的最少操作次数。

如果不可能，则输出 $-1$。

样例

输入 1

3
2
MITIT
2
TITMI
2
MTIIT

输出 1

0
1
-1

说明

对于第一个测试用例，顺序 $\text{MITIT}$ 已经能让海狸贝克高兴，因此答案为 $0$。

对于第二个测试用例，你可以将字符串拆分为 $\text{TITIT}$ 和 $\text{MI}$，然后交换这两部分得到 $\text{MITIT}$。因此，答案为 $1$。

对于第三个测试用例，可以证明没有任何操作序列能产生 $\text{MITIT}$，因此答案为 $-1$。