1587:CCPC

时间限制: 1 S | 内存限制: 65536 KB
Accept: 11 | Submit: 47
[提交] [状态] [讨论版]
描述

CCPC(China Collegiate Programming Contest,中国大学生程序设计竞赛)的简称。

现在给你一个仅由大写字符'C','P','X'组成的字符串 s,问你所有不相交的子序列之中,能构成"CCPC"最大个数是多少。


例如:

1. 字符串”CCPCCPC",因为子序列不能相交,其子序列最多构成1个“CCPC"。

2. 字符串”CCXCCPXXCPC",其子序列最多构成2个“CCPC"。

子序列定义:对于字符串s,由原序列中的字符排列成的所有串,每个串中字符的顺序要与原序列保持一致。

例如:"123",它的子序列是:“1”,“2”,“3”,"12",“13”,“23”,“123”,

相交指的是两个子序列有交集,其中"12"和“23”是相交的子序列,因为共同拥有原字符串的的第二个字符。


输入

第一行是一个正整数 T 代表测试案例的数量。(1 <= T <= 1000)

每组案例包含一个仅由英文字母组成的字符串 s。(1 <= s.size() <= 1e4)

输出

针对每组案例,输出不相交子序列构成得"CCPC"个数的最大值,然后换行。

样例输入

2

CCPCCPC

CCXCCPXXCPC

样例输出

1

2

HINT


来源
2021-TKK-ICPC Summer Training Camp Round #2