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.

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}$.