Хоссам решил проникнуть в комнату Хемоса, пока он спит, и сменить пароль на его ноутбуке. Он уже знает исходный пароль, равный строке \(s\) длины \(n\). Он также знает, что существуют \(k\) особых букв в алфавите: \(c_1,c_2,\ldots, c_k\).
Хоссам написал программу, которая делает следующее.
- Программа рассматривает текущий пароль \(s\) некоторой длины \(m\).
- Затем она находит все такие позиции \(i\) (\(1\le i<m\)), что \(s_{i+1}\) — одна из \(k\) особых букв.
- После этого она удаляет все символы на таких позициях из пароля \(s\) даже если \(s_{i}\) — особая буква. Если таких позиций нет, программа выдает ошибку с очень громким звуком.
Например, пусть строка \(s\) равна «abcdef», а особые буквы — «b» и «d». Если Хоссам запустит программу один раз, символы на позициях \(1\) и \(3\) будут удалены, так как они находятся перед особыми символами, и пароль станет равным «bdef». Если он запустит программу еще раз, она удалит символ на позиции \(1\), и пароль станет «def». Хоссам поступит разумно, если не будет запускать программу в третий раз.
Хоссам хочет узнать, сколько максимум раз он может запустить программу на ноутбуке Хемоса, не разбудив его сигналом ошибки. Можете помочь ему?
Выходные данные
Для каждого набора входных данных выведите максимальное количество раз, которое Хоссам может запустить программу, не вызвав ошибку.
Примечание
В первом наборе входных данных программу можно запустить \(5\) раз: \(\text{iloveslim} \to \text{ilovslim} \to \text{iloslim} \to \text{ilslim} \to \text{islim} \to \text{slim}\)
Во втором наборе входных данных программу можно запустить \(2\) раза: \(\text{joobeel} \to \text{oel} \to \text{el}\)
В третьем наборе входных данных программу можно запустить \(3\) раза: \(\text{basiozi} \to \text{bioi} \to \text{ii} \to \text{i}\).
В четвертом наборе входных данных программу можно запустить \(5\) раз: \(\text{khater} \to \text{khatr} \to \text{khar} \to \text{khr} \to \text{kr} \to \text{r}\)
В пятом наборе входных данных программу можно запустить только раз: \(\text{abobeih} \to \text{h}\)
В шестом наборе программу нельзя запустить ни разу, так как пароль не содержит особых символов.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10
9
iloveslim
1 s
7
joobeel
2 o e
7
basiozi
2 s i
6
khater
1 r
7
abobeih
6 a b e h i o
5
zondl
5 a b c e f
6
shoman
2 a h
7
shetwey
2 h y
5
samez
1 m
6
mouraz
1 m
|
5
2
3
5
1
0
3
5
2
0
|