题目描述

Tasky 的快速进步引来了恶意攻击者，他们试图测试 Tasky 的极限。研究人员发现了一类基于 $N$ 个攻击单词 $W_1,W_2,\ldots,W_N$ 的“对抗提示”。每个 $W_i$ 都由小写英文字母 a 到 z 组成。如果 Tasky 的输入中按顺序包含这些单词，它就会崩溃。

这些单词并不一定需要互不重叠地出现在输入中。只要存在一个字符串 $S$，使得所有 $N$ 个攻击单词都能作为子串按顺序出现在 $S$ 中，并且 $S$ 中的每个字符都至少被某个攻击单词的出现区间覆盖，那么 $S$ 就是一个有效的攻击超串。

形式化地，长度为 $L$ 的字符串 $S_{1..L}$ 有效，当且仅当存在 $N$ 个区间 $[L_i,R_i]$，满足：

1. 对每个 $i=1..N$，攻击单词 $W_i$ 出现在区间 $[L_i,R_i]$ 上，即$$S_{L_i..R_i}=W_i.$$
2. 对所有 $i<j$，都有$$L_i\le L_j\quad\text{且}\quad R_i\le R_j,$$ 也就是说，这些攻击单词必须按 $W_1,W_2,\ldots,W_N$ 的顺序出现。
3. $S$ 中每个位置都必须至少属于一个区间，即不允许出现任何没有被攻击单词覆盖的多余字符。

对于每个 $L=1..K$，你需要判断是否存在长度为 $L$ 的有效攻击超串。请输出所有可行长度 $L$ 的总和。

注意，输入中的单词以压缩形式给出。第 $i$ 个单词 $W_i$ 的压缩形式记为 $C_i$。

压缩格式

压缩串只包含字母和数字。若出现一段数字，它表示后面紧跟的那个字符重复出现的次数。

例如：

• c3po 解压后为 cpppo；
• 11ab 解压后为 aaaaaaaaaaab。

输入格式

输入第一行包含一个整数 $T$，表示测试用例数。

对于每个测试用例：

第一行包含两个整数 $N,K$。

接下来 $N$ 行，第 $i$ 行包含压缩后的攻击单词 $C_i$。

输出格式

对于第 $i$ 个测试用例，输出：

Case #i: ans

其中 $ans$ 为所有存在有效攻击超串的长度之和。

数据范围

• $1\le T\le 90$
• $1\le N\le 2000$
• $1\le K\le 10^6$
• $1\le |C_i|\le 2000$，即每个压缩单词长度不超过 $2000$
• $1\le |W_i|\le 10^6$，即每个解压后的单词长度不超过 $10^6$
• 至多 $4$ 个测试用例中存在解压长度大于 $10^4$ 的单词
• 解压后字符串总长度没有显式上界

样例输入

6
3 9
sand
andy
meta
2 9
banana
anana
1 5
apple
2 10
1a2a3a
aab
2 8
bora
bora
2 10
tournament
tour

样例输出

Case #1: 9
Case #2: 14
Case #3: 5
Case #4: 24
Case #5: 12
Case #6: 0

样例解释

第一个样例中，长度 $1$ 到 $8$ 都不存在有效攻击超串，但长度 $9$ 的 sandymeta 是有效的：其中 sand 位于 $1\ldots 4$，andy 位于 $2\ldots 5$，meta 位于 $6\ldots 9$。因此答案为 $9$。

第二个样例中，banana（长度 $6$）和 bananana（长度 $8$）是两个有效攻击超串，因此答案为 $6+8=14$。

第四个样例中，两个解压后的单词分别为 aaaaaa 和 aab。有效攻击超串为 aaaaaab（长度 $7$）、aaaaaaab（长度 $8$）和 aaaaaaaab（长度 $9$）。注意，例如 aaaaaacaab 不合法，因为其中字符 c 没有被任何攻击单词的区间覆盖。因此答案为 $7+8+9=24$。