A - Again Make UTPC Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

長さ 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 個のテストケースが与えられるので、それぞれについて答えてください。

制約

  • 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 以下

入力

入力は以下の形式で標準入力から与えられる。ここで、\mathrm{case}_i は i 番目のテストケースを意味する。

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

各ケースは以下の形式で与えられる。

N
S

出力

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

入力例 1

3
10
UCUCTPUCUC
5
UTCUP
12
TUPCTTPCUTPC

出力例 1

2
-1
0

1 番目のテストケースでは、次の 2 回の操作で可能です。1 回以下の操作では、条件を満たすようにできません。

  • (i, j) = (1, 4) を選び、CCUUTPUCUC とする。
  • (i, j) = (7, 10) を選び、CCUUTPCCUU とする。

2 番目のテストケースでは、どのように操作しても、条件を満たすようにできません。

3 番目のテストケースでは、操作を行う必要がありません。