A. Tart Splitting
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Baker Beaver has prepared a long fruit tart. This tart is decorated with a sequence of $$$2N+1$$$ toppings: $$$N$$$ pieces of Indigo berries, $$$N$$$ pieces of Tangerine slices, and exactly one Marzipan star. Baker Beaver will be happy if the toppings are arranged in the form $$$\texttt{M} \underbrace{\texttt{ITIT}\dots\texttt{IT}}_{N\text{ times}}$$$. That is, the first topping should be $$$\texttt{M}$$$, and then $$$\texttt{I}$$$ and $$$\texttt{T}$$$ should alternate, beginning with $$$\texttt{I}$$$.

However, in the morning rush, the toppings were placed in a scrambled order, represented by a string $$$s$$$ of length $$$2N+1$$$ consisting of the characters $$$\texttt{M}$$$, $$$\texttt{I}$$$, and $$$\texttt{T}$$$. To fix the tart without ruining the crust, you may perform the following operation any number of times (possibly zero):

  • Choose an index $$$i$$$ ($$$1 \le i \lt |s|$$$), split the string into two parts $$$s[1 \dots i]$$$ and $$$s[i+1 \dots |s|]$$$, and then swap the two parts to obtain the new string $$$s[i+1 \dots |s|] + s[1 \dots i]$$$.
Find the minimum number of operations needed to make Baker Beaver happy. If it is impossible, output $$$-1$$$.
Input

Each test contains multiple test cases. The first line contains a single integer $$$T$$$ ($$$1 \le T \le 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$N$$$ ($$$1 \le N \le 10^5$$$).

The second line of each test case contains a string $$$s$$$ of length $$$2N+1$$$, consisting of $$$N$$$ occurrences of $$$\texttt{I}$$$, $$$N$$$ occurrences of $$$\texttt{T}$$$, and exactly one occurrence of $$$\texttt{M}$$$.

The sum of $$$N$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print a single integer — the minimum number of operations required to make Baker Beaver happy.

If it is impossible, print $$$-1$$$ instead.

Example
Input
3
2
MITIT
2
TITMI
2
MTIIT
Output
0
1
-1
Note

For the first test case, the order $$$\texttt{MITIT}$$$ will already make Baker Beaver happy, so the answer is $$$0$$$.

For the second test case, you can split the string into $$$\texttt{TITIT}$$$ and $$$\texttt{MI}$$$, then swap the two parts to obtain $$$\texttt{MITITIT}$$$. Thus, the answer is $$$1$$$.

For the third test case, it can be shown that no sequence of operations can produce $$$\texttt{MITIT}$$$, so the answer is $$$-1$$$.