D. Падежи
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы лингвист, изучающий загадочный древний язык. Вы знаете, что

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

Выходные данные

Для каждого набора входных данных выведите одну строку, состоящую из одного целого числа, — минимальное количество падежей в языке.

Пример
Входные данные
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'.