P16771 [GKS 2020 #G] Kick_Start

Ksenia 非常喜欢阅读，因此她每天都会在开始晨间其他活动之前，先读一段她最喜欢的书。片段就是文本的一个子串。Ksenia 有点迷信，她相信如果她阅读的片段以字符串 `KICK` 开头，然后跟有 $0$ 个或多个字符，最后以字符串 `START` 结尾，那么她的一天就会是幸运的，即使整个片段没有实际意义。 给定书籍的文本，请统计在书籍变旧需要购买新书之前，Ksenia 可以阅读的不同幸运片段的数量。两个片段如果在文本中的起始位置或结束位置不同，则视为不同，即使它们读起来相同。同时注意，不同的幸运片段可能重叠。

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 行，每行包含一个仅由大写英文字母组成的字符串 $S$。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是该测试用例文本中不同幸运片段的数量。

第一个测试用例中有三个幸运片段，即 `KICKSTARTPROBLEMNAMEDKICKSTART` 以及两个 `KICKSTART`。第二个测试用例的文本中没有幸运片段。 ### 限制条件 $1 \le T \le 100$。 $S$ 仅由大写英文字母组成。 **测试集 1** $1 \le |S| \le 1000$。 **测试集 2** $1 \le |S| \le 10^5$。 翻译由 DeepSeek V4 Pro 完成