题目描述

Ksenia 非常喜欢阅读，因此她每天都会在开始晨间其他活动之前，先读一段她最喜欢的书。片段就是文本的一个子串。Ksenia 有点迷信，她相信如果她阅读的片段以字符串 KICK 开头，然后跟有 $0$ 个或多个字符，最后以字符串 START 结尾，那么她的一天就会是幸运的，即使整个片段没有实际意义。

给定书籍的文本，请统计在书籍变旧需要购买新书之前，Ksenia 可以阅读的不同幸运片段的数量。两个片段如果在文本中的起始位置或结束位置不同，则视为不同，即使它们读起来相同。同时注意，不同的幸运片段可能重叠。

输入格式

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

输出格式

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

3
AKICKSTARTPROBLEMNAMEDKICKSTART
STARTUNLUCKYKICK
KICKXKICKXSTARTXKICKXSTART

Case #1: 3
Case #2: 0
Case #3: 5

提示

第一个测试用例中有三个幸运片段，即 KICKSTARTPROBLEMNAMEDKICKSTART 以及两个 KICKSTART。第二个测试用例的文本中没有幸运片段。

限制条件

$1 \le T \le 100$。

$S$ 仅由大写英文字母组成。

测试集 1

$1 \le |S| \le 1000$。

测试集 2

$1 \le |S| \le 10^5$。

翻译由 DeepSeek V4 Pro 完成