У Тонио есть клавиатура с двумя клавишами: буквой «V» и буквой «K».
Однажды он набрал строку s, используя только эти две буквы. Ему нравится, когда он встречает подстроку «VK», поэтому он хочет изменить не больше одной буквы в строке (или не изменять ничего), чтобы максимизировать число вхождений этой подстроки. Вычислите максимальное число раз, которое строка «VK» может встретиться как подстрока (т. е. буква «K» сразу после буквы «V») в получившейся строке.
Выходные данные
Выведите одно число — максимальное число раз, которое строка «VK» может встречаться как подстрока в данной строке после изменения не более одного символа.
Примечание
В первом примере можно ничего не изменять, строка «VK» встречается один раз, что является максимумом.
Во втором примере можно изменить второй символ с «V» на «K». Тогда мы получим строку «VK», которая имеет одно вхождение строки «VK» как подстроки.
В четвертом примере мы можем изменить четвертую букву с «K» на «V». Это даст нам строку «VKKVKKKKKKVVVVVVVVVK». В ней строка «VK» встречается как подстрока трижды. Можно показать, что любое другое действие не дает нам больше вхождений.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
VK
|
1
|
|
2
|
VV
|
1
|
|
3
|
V
|
0
|
|
4
|
VKKKKKKKKKVVVVVVVVVK
|
3
|
|
5
|
KVKV
|
1
|