← 返回题目列表

AtCoder · utpc2023_a

A. 再次制作UTPC

中文机器翻译题面 查看原题

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