Вы лингвист, изучающий загадочный древний язык. Вы знаете, что
- Его слова состоят только из первых \(c\) букв латинского алфавита.
- Каждое слово имеет падеж, который можно однозначно определить по его последней букве (разные буквы соответствуют разным падежам). Например, слова "ABACABA" и "ABA" (если они существуют) имеют одинаковый падеж в этом языке, потому что у них обоих одинаковое окончание 'A', в то время как "ALICE" и "BOB" принадлежат разным падежам. Если в языке нет падежа, соответствующего какой-либо букве, это означает, что слово не может заканчиваться на эту букву.
- Длина каждого слова составляет \(k\) или меньше.
У вас есть один текст, написанный на этом языке. К сожалению, поскольку язык действительно древний, пробелы между словами отсутствуют, и все буквы заглавные. Вам интересно, каково минимальное количество падежей может быть в этом языке. Можете ли вы это выяснить?
Выходные данные
Для каждого набора входных данных выведите одну строку, состоящую из одного целого числа, — минимальное количество падежей в языке.
Примечание
В первом наборе входных данных в языке должно быть пять падежей (для каждой из букв 'A', 'B', 'C', 'D', и 'E' должен быть падеж, который имеет соответствующее окончание).
В четвертом наборе входных данных достаточно одного падежа с окончанием 'B'.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|