Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

A. Новое имя Юры
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

После проведения «ЛКОШПа» мальчик Юра очень устал и захотел изменить свою жизнь и переехать в Японию. В честь такой перемены Юра сменить имя на что-то милое.

Загоревшись этой идеей он уже придумал себе имя $$$s$$$, состоящее только из символов «_» и «^». Но вот незадача Юра очень любит смайлики «^_^» и «^^». Поэтому любой символ имени должен быть частью хотя бы одного такого смайлика. Обратите внимание, что смайликом могут являться только подряд идущие символы имени.

Более формально, рассмотрим все вхождения строк «^_^» и «^^» в строку $$$s$$$. Тогда все такие вхождения должны покрывать всю строку $$$s$$$, возможно, с пересечениями. Например, в строке «^^__^_^^__^» символы на позициях $$$3,4,9,10$$$ и $$$11$$$ не содержатся внутри ни одного смайлика, а остальные символы на позициях $$$1,2,5,6,7$$$ и $$$8$$$ содержатся внутри смайликов.

За одну операцию Юра может вставить один из символов «_» и «^» в своё имя $$$s$$$ (вставлять можно на любую позицию в строке). Он просит вас сказать минимальное количество операций, которые нужно сделать, чтобы имя подходило под критерий Юры.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая и единственная строка каждого набора входных данных содержит единственную строку $$$s$$$ ($$$1 \leq |s| \leq 100$$$), состоящую из символов «_» и «^»,  — имя, которое нужно поменять.

Выходные данные

Для каждого набора входных данных выведите ровно одно целое число — минимальное количество символов, которое нужно добавить в имя, чтобы оно подходило для Юры. Если ничего в имени менять не нужно, то выведите $$$0$$$.

Пример
Входные данные
7
^______^
___^_^^^_^___^
^_
^
^_^^^^^_^_^^
___^^
_
Выходные данные
5
5
1
1
0
3
2
Примечание

В первом наборе входных данных можно получить следующее имя, добавив $$$5$$$ символов:

^_^_^_^_^_^_^

В третьем наборе входных данных мы можем добавить один символ «^» в конец имени, тогда получится имя:

^_^

В четвёртом наборе входных данных мы можем добавить один символ «^» в конец имени, тогда получится имя:

^^

В пятом наборе входных данных все символы уже содержатся в смайликах, поэтому ответ равен $$$0$$$.

В седьмом наборе входных данных можно добавить один символ «^» в начало имени и один символ «^» в конец имени, тогда получится имя:

^_^