给定一个长度为 $N$ 的字符串 $S$，其中每个字符均为 U、T、P 或 C。

你可以进行零次或多次以下操作： * 选择一对整数 $(i, j)$，满足 $1 \le i \le j \le N$。将 $S$ 中从第 $i$ 个字符到第 $j$ 个字符的子串按字母升序排序。

请判断是否能满足以下条件，如果可以，计算所需的最少操作次数： * $S$ 包含 UTPC 作为连续子串。

你需要解决 $T$ 组测试用例。

输入格式

输入通过标准输入给出，格式如下，其中 $case_i$ 表示第 $i$ 组测试用例：

$T$ $case_1$ $case_2$ $\vdots$ $case_T$

每组测试用例的格式如下：

$N$ $S$

• $T, N$ 为整数。
• $1 \le T \le 2 \times 10^5$
• $1 \le N \le 2 \times 10^5$
• $S$ 是一个由 U、T、P 和 C 组成的长度为 $N$ 的字符串。
• 对于每个输入文件，所有测试用例的 $N$ 之和不超过 $2 \times 10^5$。

输出格式

输出 $T$ 行。第 $i$ 行应包含第 $i$ 组测试用例的答案。具体而言，如果可以满足条件，输出最少操作次数；如果无法满足，输出 -1。

样例

样例输入 1

3
10
UCUCTPUCUC
5
UTCUP
12
TUPCTTPCUTPC

样例输出 1

2
-1
0

说明

对于第一组测试用例，可以通过以下两次操作满足条件。仅进行一次操作无法满足。 选择 $(i, j) = (1, 4)$，$S$ 变为 CCUUTPUCUC。 选择 $(i, j) = (7, 10)$，$S$ 变为 CCUUTPCCUU。

对于第二组测试用例，无法满足条件。

对于第三组测试用例，无需进行操作即可满足条件。