分数: 500 点
问题陈述
给你一个字符串 S 组成 A, B,和 C.
您可以执行以下操作零次或多次。
- 选择一个子串(连续子序列) S 即
A,AB,或ABC,然后将其删除。剩余的字符被连接起来,保留它们的顺序。
找出以下的最小可能长度 S 最后。
T 给出了测试用例;解决它们中的每一个。
约束
- T 是介于 1 和 10^5,包括在内。
- S 是一个由以下组成的字符串
A,B,和C长度介于 每个输入中的 1 和 10^6,包括在内。 - 总和 一个输入文件中的 |S| 最多为 10^6.
输入
输入由标准输入按以下格式给出,其中 \mathrm{case}_i 表示 i-第一个测试用例:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
每个测试用例均按以下格式给出:
S
输出
输出 T 行。的 i- 第行应包含以下问题的答案 i- 第一个测试用例。
示例输入 1
5 CAABCB B AAABBC AABBCC CABCCBCBAABCBBBAABAABACABBC
示例输出 1
1 1 0 1 7
此输入包含五个测试用例。
对于第一个测试用例,我们可以执行如下操作。
- 选择并删除第三个到第五个字符 S=
CAABCB。手术后, S 变为CAB. - 选择并删除第二个到第三个字符 S=
CAB。手术后, S 变为C. - 无法执行进一步操作。 S=
C有长度 1,这是可实现的最小值。