B. Impost or Sus
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A string $$$w$$$ consisting of lowercase Latin letters is called suspicious if and only if all of the following conditions hold:

  • The letter $$$\mathtt{s}$$$ appears at least twice, and
  • For every occurrence of the letter $$$\mathtt{u}$$$, the two nearest occurrences of $$$\mathtt{s}$$$ are the same number of characters away from the $$$\mathtt{u}$$$.

After watching you finish a string task, your friend Aka has gifted you a string $$$r$$$ consisting only of letters $$$\mathtt{s}$$$ and $$$\mathtt{u}$$$. You can perform the following operation on $$$r$$$:

  • Choose an index $$$i$$$ ($$$1\le i\le |r|$$$), and set $$$r_i$$$ to $$$\mathtt{s}$$$.

Determine the minimum number of operations needed to make $$$r$$$ suspicious. It can be shown that, under the given constraints, it is always possible to transform $$$r$$$ into a suspicious string.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The only line of each test case contains the string $$$r$$$ ($$$3\le |r|\le 2\cdot 10^5$$$). It is guaranteed that $$$r_i = \mathtt{s}$$$ or $$$\mathtt{u}$$$.

It is guaranteed that the sum of $$$|r|$$$ over all test cases does not exceed $$$2\cdot 10 ^ 5$$$.

Output

For each test case, output a single integer — the minimum number of operations needed to make $$$r$$$ suspicious.

Example
Input
9
sus
uuuu
sssss
uusuuu
suuuuuu
usssssss
sssuuusss
susuusuuus
uuuuuuuuuuu
Output
0
3
0
3
3
1
1
2
6
Note

In the first test case, the string $$$\mathtt{sus}$$$ is already suspicious because $$$\mathtt{s}$$$ appears twice in the string and the two nearest $$$\mathtt{s}$$$ to the only $$$\mathtt{u}$$$ are both $$$1$$$ character away: $$$\color{red}{\mathtt{s}}\underline{\mathtt{u}}\color{red}{\mathtt{s}}$$$.

In the second test case, it is optimal to perform the operation on indices $$$1$$$, $$$3$$$, and $$$4$$$. After that, the string $$$s$$$ becomes $$$\texttt{suss}$$$. The string $$$\mathtt{suss}$$$ is suspicious because $$$\mathtt{s}$$$ appears $$$3$$$ times in the string and the two nearest $$$\mathtt{s}$$$ to the only $$$\mathtt{u}$$$ are both $$$1$$$ character away: $$$\color{red}{\mathtt{s}}\underline{\mathtt{u}}\color{red}{\mathtt{s}}\mathtt{s}$$$.

In the third test case, the condition on $$$\mathtt{u}$$$ is vacuously true because there is no $$$\mathtt{u}$$$ in the string $$$\mathtt{sssss}$$$. Thus, the given string is already suspicious.

In the sixth test case, the initial string $$$\mathtt{usssssss}$$$ is not suspicious because the two nearest $$$\mathtt{s}$$$ to the only $$$\mathtt{u}$$$ are one and two characters away, respectively: $$$\underline{\mathtt{u}}\color{red}{\mathtt{ss}}\mathtt{sssss}$$$.