После проведения «ЛКОШПа» мальчик Юра очень устал и захотел изменить свою жизнь и переехать в Японию. В честь такой перемены Юра сменить имя на что-то милое.
Загоревшись этой идеей он уже придумал себе имя \(s\), состоящее только из символов «_» и «^». Но вот незадача Юра очень любит смайлики «^_^» и «^^». Поэтому любой символ имени должен быть частью хотя бы одного такого смайлика. Обратите внимание, что смайликом могут являться только подряд идущие символы имени.
Более формально, рассмотрим все вхождения строк «^_^» и «^^» в строку \(s\). Тогда все такие вхождения должны покрывать всю строку \(s\), возможно, с пересечениями. Например, в строке «^^__^_^^__^» символы на позициях \(3,4,9,10\) и \(11\) не содержатся внутри ни одного смайлика, а остальные символы на позициях \(1,2,5,6,7\) и \(8\) содержатся внутри смайликов.
За одну операцию Юра может вставить один из символов «_» и «^» в своё имя \(s\) (вставлять можно на любую позицию в строке). Он просит вас сказать минимальное количество операций, которые нужно сделать, чтобы имя подходило под критерий Юры.
Выходные данные
Для каждого набора входных данных выведите ровно одно целое число — минимальное количество символов, которое нужно добавить в имя, чтобы оно подходило для Юры. Если ничего в имени менять не нужно, то выведите \(0\).
Примечание
В первом наборе входных данных можно получить следующее имя, добавив \(5\) символов:
^_^_^_^_^_^_^
В третьем наборе входных данных мы можем добавить один символ «^» в конец имени, тогда получится имя:
^_^
В четвёртом наборе входных данных мы можем добавить один символ «^» в конец имени, тогда получится имя:
^^
В пятом наборе входных данных все символы уже содержатся в смайликах, поэтому ответ равен \(0\).
В седьмом наборе входных данных можно добавить один символ «^» в начало имени и один символ «^» в конец имени, тогда получится имя:
^_^
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
^______^
___^_^^^_^___^
^_
^
^_^^^^^_^_^^
___^^
_
|
5
5
1
1
0
3
2
|