B. Уплывая вдаль
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Перед домом Монокарпа протекает река, которую можно представить в виде полоски из клеток. В некоторых клетках сильное течение, а в остальных нет течения. Задается она в виде строки $$$s$$$, состоящей из следующих символов:

  • знак «меньше» ('<') — течение влево;
  • знак «больше» ('>') — течение вправо;
  • звёздочка ('*') — нет течения.

Сначала Монокарп выбирает, в какой клетке начать свое путешествие по реке.

Если в клетке есть течение, то Монокарпа относит в соседнюю клетку в направлении течения. Если соседней клетки нет (то есть, течение влево в клетке $$$1$$$ или течение вправо в клетке $$$n$$$), то Монокарп оказывается на берегу. Каждое перемещение занимает одну минуту.

Если в клетке нет течения, то Монокарп гребет в соседнюю клетку слева или в соседнюю клетку справа. Если соседней клетки в выбранном Монокарпом направлении нет, то он окажется на берегу. Каждое перемещение также занимает одну минуту.

Монокарп хочет путешествовать по реке как можно дольше. Если Монокарп может путешествовать бесконечно, выведите $$$-1$$$. Иначе выведите максимальное время, которое Монокарп может путешествовать по реке, пока не окажется на берегу.

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

В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

В единственной строке каждого набора входных данных записана строка $$$s$$$ ($$$1 \le |s| \le 3 \cdot 10^5$$$), состоящая только из символов '<' (течение влево), '>' (течение вправо), '*' (нет течения). ASCII коды $$$60$$$, $$$62$$$ и $$$42$$$, соответственно.

Дополнительное ограничение на входные данные: суммарная длина строк $$$s$$$ по всем наборам входных данных не превосходит $$$3 \cdot 10^5$$$.

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

На каждый набор входных данных выведите одно целое число:

  • $$$-1$$$, если Монокарп может путешествовать по реке бесконечно;
  • максимальное время, которое Монокарп может путешествовать по реке, пока не окажется на берегу, в противном случае.
Пример
Входные данные
4
*****
<<<>
>*<
*
Выходные данные
-1
3
-1
1