AT_utpc2023_a Again Make UTPC

给定一个长度为 $N$ 的字符串 $S$，$S$ 的每个字符均为 `U`、`T`、`P`、`C` 之一。 你可以进行如下操作任意多次（也可以不操作）： - 任选一组整数对 $(i, j)$，满足 $1 \leq i \leq j \leq N$。将 $S$ 中第 $i$ 个字符到第 $j$ 个字符按字母升序排序。 请判断能否通过若干次（可为 0 次）上述操作，使字符串 $S$ 满足以下条件： - $S$ 包含连续的子串 `UTPC`。 对于 $T$ 个测试用例，请对每个案例给出答案：若可行，输出最少需要的操作次数；否则输出 `-1`。

输入以以下格式从标准输入读入。$\mathrm{case}_i$ 表示第 $i$ 个测试用例。 > $T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$ 每个测试用例如下： > $N$ $S$

输出 $T$ 行，第 $i$ 行输出第 $i$ 个测试用例的答案。若可以使字符串 $S$ 满足条件，则输出所需操作的最小次数；否则输出 $-1$。

### 样例解释 1 对于第 1 个测试用例，只需进行如下 2 次操作。若操作次数小于 2，则无法满足条件。 - 选择 $(i, j) = (1, 4)$，字符串变为 `CCUUTPUCUC`。 - 选择 $(i, j) = (7, 10)$，字符串变为 `CCUUTPCCUU`。 对于第 2 个测试用例，无论如何操作，都无法满足条件。 对于第 3 个测试用例，不需要任何操作即可满足条件。 ### 约束条件 - $T, N$ 为整数 - $1 \leq T \leq 2 \times 10^5$ - $1 \leq N \leq 2 \times 10^5$ - $S$ 仅包含 `U`、`T`、`P`、`C`，长度为 $N$ - 所有测试用例中 $N$ 的总和不超过 $2 \times 10^5$ 由 ChatGPT 5 翻译