Codeforces Round 961 (Div. 2) |
---|
Закончено |
Вы лингвист, изучающий загадочный древний язык. Вы знаете, что
У вас есть один текст, написанный на этом языке. К сожалению, поскольку язык действительно древний, пробелы между словами отсутствуют, и все буквы заглавные. Вам интересно, каково минимальное количество падежей может быть в этом языке. Можете ли вы это выяснить?
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$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}$$$.
Для каждого набора входных данных выведите одну строку, состоящую из одного целого числа, — минимальное количество падежей в языке.
75 5 1ABCDE3 1 2AAA3 2 2AAB10 2 2ABABABABAB4 4 4DCBA1 17 1Q9 3 2ABCABCABC
5 1 2 1 1 1 2
В первом наборе входных данных в языке должно быть пять падежей (для каждой из букв 'A', 'B', 'C', 'D', и 'E' должен быть падеж, который имеет соответствующее окончание).
В четвертом наборе входных данных достаточно одного падежа с окончанием 'B'.
Название |
---|