D. 格（Cases）
每个测试的时间限制：2 秒
每个测试的内存限制：256 兆字节

你是一位语言学家，正在研究一种神秘的古代语言。你知道：

• 这种语言的单词只由拉丁字母表中前 $c$ 个字母组成。
• 每个单词都有一个“格”，该格可以由单词的最后一个字母唯一确定（不同的字母对应不同的格）。例如，单词 "ABACABA" 和 "ABA"（如果存在）具有相同的格，因为它们都以字母 'A' 结尾；而 "ALICE" 和 "BOB" 具有不同的格。如果这种语言没有对应某个字母的格，那就意味着单词不能以该字母结尾。
• 每个单词的长度不超过 $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}$。

输出
对于每个测试用例，输出一行一个整数——语言中最少的格数。

示例
输入

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

输出

5
1
2
1
1
1
2

注意

• 在第一个测试用例中，语言中必须有五个格（字母 'A'、'B'、'C'、'D' 和 'E' 各自对应一个格）。
• 在第四个测试用例中，一个以 'B' 结尾的格就足够了。