CF1995D.Cases

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

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}$。

对于每个测试用例，输出一行一个整数，表示该语言最少需要的格的数量。

在第一个测试用例中，语言必须有五种格（分别对应 'A'、'B'、'C'、'D'、'E' 这五个字母，每个字母都必须有对应的格）。

在第四个测试用例中，仅需要一种以 'B' 结尾的格即可。

由 ChatGPT 4.1 翻译