P1061挑战不被发现（apt）

【题目背景】

Gioush 大队营地里开始循环播放《APT.》。为了挑战唱《APT.》不被发现，你需要尽可能减少播放记录中连续子串 APT 的出现次数。

【题目描述】

给定一个只包含大写英文字母的字符串 $S$。如果存在位置 $i$ 使 $S_iS_{i+1}S_{i+2}=\texttt{APT}$，则记作一次 APT 记录，不同起点分别计数。

你至多可以选择一个非空区间 $[l,r]$ 并将 $S_lS_{l+1}\cdots S_r$ 反转，也可以不进行操作。求操作结束后 APT 记录数量的最小值。

【输入格式】

第一行包含两个非负整数 $c,T$，分别表示测试点编号和测试数据组数。样例中 $c=0$，正式测试数据中 $1\le c\le20$。

接下来 $T$ 行，每行包含一个只由大写英文字母组成的字符串 $S$。

【输出格式】

输出 $T$ 行。第 $i$ 行包含一个整数，表示第 $i$ 个字符串经过至多一次操作后 APT 记录数量的最小值。

【样例输入】

10 12BEDAPT

【样例输出】

10

【说明】

将最后三个字符 APT 反转为 TPA 后，字符串中不再含有 APT。

对于 $100\%$ 的数据，$1\le T\le20$，$1\le |S_i|\le10^6$，且 $\sum |S_i|\le10^6$。