配点 : 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 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 在第几号测试用例中,无需进行操作。