B. Предатель или sus
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Строка $$$w$$$, состоящая из строчных латинских букв, называется подозрительной, если и только если выполняются все следующие условия:

  • Буква $$$\mathtt{s}$$$ появляется как минимум дважды, и
  • Для каждого вхождения буквы $$$\mathtt{u}$$$ два ближайших вхождения буквы $$$\mathtt{s}$$$ находятся на одинаковом расстоянии от $$$\mathtt{u}$$$.

После того как вы решили задачу на строку, ваш друг Ака подарил вам строку $$$r$$$, состоящую только из букв $$$\mathtt{s}$$$ и $$$\mathtt{u}$$$. Вы можете выполнять следующую операцию над $$$r$$$:

  • Выбрать индекс $$$i$$$ ($$$1\le i\le |r|$$$) и сделать $$$r_i$$$ равным $$$\mathtt{s}$$$.

Вам нужно определить минимальное количество операций, необходимых для того, чтобы сделать $$$r$$$ подозрительной. Можно показать, что при заданных ограничениях всегда возможно преобразовать $$$r$$$ в подозрительную строку.

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

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

Единственная строка каждого набора входных данных содержит строку $$$r$$$ ($$$3\le |r|\le 2\cdot 10^5$$$). Гарантируется, что $$$r_i = \mathtt{s}$$$ или $$$\mathtt{u}$$$.

Гарантируется, что сумма значений $$$|r|$$$ по всем наборам входных данных не превосходит $$$2\cdot 10 ^ 5$$$.

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

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

Пример
Входные данные
9
sus
uuuu
sssss
uusuuu
suuuuuu
usssssss
sssuuusss
susuusuuus
uuuuuuuuuuu
Выходные данные
0
3
0
3
3
1
1
2
6
Примечание

В первом наборе входных данных строка $$$\mathtt{sus}$$$ уже подозрительная, потому что $$$\mathtt{s}$$$ появляется дважды в строке, и два ближайших $$$\mathtt{s}$$$ к единственному $$$\mathtt{u}$$$ находятся на расстоянии $$$1$$$ символа: $$$\color{red}{\mathtt{s}}\underline{\mathtt{u}}\color{red}{\mathtt{s}}$$$.

Во втором наборе входных данных оптимально выполнить операцию на индексах $$$1$$$, $$$3$$$ и $$$4$$$. После этого строка $$$s$$$ становится $$$\texttt{suss}$$$. Строка $$$\mathtt{suss}$$$ является подозрительной, потому что $$$\mathtt{s}$$$ появляется $$$3$$$ раза в строке, и два ближайших $$$\mathtt{s}$$$ к единственному $$$\mathtt{u}$$$ находятся на расстоянии $$$1$$$ символа: $$$\color{red}{\mathtt{s}}\underline{\mathtt{u}}\color{red}{\mathtt{s}}\mathtt{s}$$$.

В третьем наборе входных данных условие для $$$\mathtt{u}$$$ является истинным, потому что в строке $$$\mathtt{sssss}$$$ нет $$$\mathtt{u}$$$. Таким образом, данная строка уже подозрительная.

В шестом наборе входных данных начальная строка $$$\mathtt{usssssss}$$$ не является подозрительной, потому что два ближайших $$$\mathtt{s}$$$ к единственному $$$\mathtt{u}$$$ находятся на расстоянии один и два символа соответственно: $$$\underline{\mathtt{u}}\color{red}{\mathtt{ss}}\mathtt{sssss}$$$.