← 返回题目列表

Codeforces · 1995/D

D. 案例

中文机器翻译题面 查看原题

你是一位研究神秘古代语言的语言学家。你知道

1. 它的单词仅由拉丁字母表的前 $$$c$$$ 字母组成。
2. 每个单词都有一个大小写,可以通过其最后一个字母明确确定(不同的字母对应不同的大小写)。例如,单词“ABACABA”和“ABA”(如果存在)在此语言中具有相同的大小写,因为它们都具有相同的结尾“A”,而“ALICE”和“BOB”具有不同的大小写。如果该语言没有某个字母对应的大小写,则意味着该单词不能以该字母结尾。
3. 每个单词的长度不超过$$$k$$$。

您有一个用这种语言编写的文本。不幸的是,由于这种语言非常古老,单词之间缺少空格,并且所有字母都是大写的。您想知道该语言可以拥有的最少案例数是多少。你能查出这个吗?

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10\,000$$$) - 测试用例的数量。接下来是测试用例的描述。

每个测试用例的第一行包含三个整数 $$$n$$$、$$$c$$$、$$$k$$$ ($$$1 \le k \le n \le 2^{18}$$$、$$$1 \le c \le 18$$$) — 文本长度、语言中字母的数量以及单词的最大长度。

第二行包含 $$$n$$$ 个字符的字符串 - 文本本身。每个字符都是拉丁字母表中前 $$$c$$$ 大写字母之一。

保证所有测试用例的$$$n$$$总和不超过$$$2^{18}$$$,并且所有测试用例的$$$2^c$$$总和不超过$$$2^{18}$$$。

输出

对于每个测试用例,输出由单个整数组成的一行——该语言中的最小用例数。

示例

输入 #1

7
5 5 1
ABCDE
3 1 2
AAA
3 2 2
AAB
10 2 2
ABABABABAB
4 4 4
DCBA
1 17 1
Q
9 3 2
ABCABCABC

输出 #1

5
1
2
1
1
1
2

注意

在第一个测试用例中,语言中必须有五个用例(对于字母“A”、“B”、“C”、“D”和“E”中的每一个都必须有一个具有相应结尾的用例)。

在第四个测试用例中,一个以“B”结尾的用例就足够了。