AT_utpc2023_a Again Make UTPC

長さ $ N $ の文字列 $ S $ が与えられます。 $ S $ の各文字は `U`, `T`, `P`, `C` のいずれかです。 あなたは、次の操作を $ 0 $ 回以上好きな回数行うことができます。 - $ 1 \leq i \leq j \leq N $ を満たす整数の組 $ (i, j) $ を $ 1 $ つ選ぶ。 $ S $ の $ i $ 文字目から $ j $ 文字目までをアルファベットの昇順に並べ替える。 文字列 $ S $ が以下の条件を満たすようにすることは可能か判定し、可能な場合は必要な操作回数の最小値を求めてください。 - $ S $ は**連続する**部分文字列として `UTPC` を含む。 $ T $ 個のテストケースが与えられるので、それぞれについて答えてください。

入力は以下の形式で標準入力から与えられる。ここで、 $ \mathrm{case}_i $ は $ i $ 番目のテストケースを意味する。 > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ 各ケースは以下の形式で与えられる。 > $ N $ $ S $

$ T $ 行出力せよ。 $ i $ 行目には、 $ i $ 番目のテストケースへの答えを出力せよ。具体的には、文字列 $ S $ が条件を満たすようにすることが可能な場合は必要な操作回数の最小値を出力し、不可能な場合は `-1` を出力せよ。

### Sample Explanation 1 $ 1 $ 番目のテストケースでは、次の $ 2 $ 回の操作で可能です。 $ 1 $ 回以下の操作では、条件を満たすようにできません。 - $ (i, j) = (1, 4) $ を選び、`CCUUTPUCUC` とする。 - $ (i, j) = (7, 10) $ を選び、`CCUUTPCCUU` とする。 $ 2 $ 番目のテストケースでは、どのように操作しても、条件を満たすようにできません。 $ 3 $ 番目のテストケースでは、操作を行う必要がありません。 ### Constraints - $ T, N $ は整数 - $ 1 \leq T \leq 2 \times 10^5 $ - $ 1 \leq N \leq 2 \times 10^5 $ - $ S $ は `U`, `T`, `P`, `C` からなる長さ $ N $ の文字列 - $ 1 $ つの入力に含まれるテストケースについて、 $ N $ の総和は $ 2 \times 10^5 $ 以下