Поликарп только что закончил записывать очередную лекцию по эльфийским языкам. На этой неделе был язык «VwV» (произносится «уву»). В письменности данного языка используются только две латинские строчные буквы 'v' и 'w'.
К сожалению, Поликарп записал лекцию курсивом и абсолютно без пробелов, поэтому вся запись выглядит как нескончаемая последовательность закорючек. Если быть точным, то Поликарп не может отличить 'w' от 'vv' в своей записи, так как и то, и другое состоит из двух одинаковых закорючек.
К счастью, его брат Монокарп пишет гораздо лучше, поэтому Поликарп смог позаимствовать его запись, и теперь хочет улучшить свою с ее помощью. Чтобы это сделать, он может следовать за записью Монокарпа и подчеркивать некоторые буквы в своей записи так, чтобы не осталось неоднозначностей. Если он подчеркивает букву 'v', то ее становится нельзя перепутать с частью буквы 'w', а если он подчеркивает 'w', то ее становится нельзя перепутать с двумя рядом стоящими буквами 'v'.
Какое минимальное количество букв необходимо подчеркнуть Поликарпу, чтобы запись стала однозначной?
Выходные данные
Для каждого набора входных данных выведите одно целое число: минимальное количество букв, которые необходимо подчеркнуть Поликарпу, чтобы запись стала однозначной.
Примечание
В первом наборе входных данных достаточно подчеркнуть одну из двух букв 'v'.
Во втором наборе входных данных буква 'v' сама по себе однозначна, поэтому не надо подчеркивать нечего.
В третьем наборе входных данных необходимо подчеркнуть 'w', чтобы не перепутать ее с двумя буквами 'v'.
В четвертом наборе входных данных можно подчеркнуть 'w', чтобы избавиться от всех неоднозначностей.
В пятом наборе входных данных можно подчеркнуть обе буквы 'w', а также одну из двух букв 'v' между ними.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
vv
v
w
vwv
vwvvwv
|
1
0
1
1
3
|