你是一位研究神秘古代语言的语言学家。你知道
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”结尾的用例就足够了。