CF2178B Impost or Sus

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.

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

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

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