You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

你正在研究一种神秘的古代语言。这种语言的单词有以下特性：

1. 单词仅由拉丁字母表前 $c$ 个字母（分别用 A, B, ..., 第 $c$ 个大写字母表示）组成。
2. 每个单词都有一个“格”，由其最后一个字母唯一确定。例如，单词 "ABACABA" 和 "ABA" 具有相同的格（因为它们都以 'A' 结尾），而 "ALICE" 和 "BOB" 则属于不同的格。如果某个字母没有对应的格，则单词不能以该字母结尾。
3. 每个单词的长度不超过 $k$。

现在，你有一段用这种语言写成的文本，但所有空格已经消失，所有字母均为大写。你需要求出，最少需要多少种格，才能使得这段文本有一种合法的划分。合法的划分是把这个字符串分成若干段，每段字符个数不超过 k，这种划分方案的花费是在任何一段的尾部出现的字符种类数，问你最小花费是多少。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。
对于每个测试用例：

• 第一行包含三个整数 $n, c, k$（$1 \le k \le n \le 2^{18}$，$1 \le c \le 18$），分别表示文本长度、字母的种类数以及单词的最大长度。
• 第二行包含一个长度为 $n$ 的字符串 $S$，由前 $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

数据范围