题目描述

一个由小写拉丁字母组成的字符串 $w$ 被称为可疑字符串，当且仅当同时满足以下所有条件：

• 字母 $\mathtt{s}$ 至少出现两次，并且
• 对于每一个 $\mathtt{u}$ 的出现，它左、右两侧最近的两个 $\mathtt{s}$ 离这个 $\mathtt{u}$ 的距离必须相同。

在你完成字符串相关任务后，你的朋友 Aka 赠送给你一个只包含字母 $\mathtt{s}$ 和 $\mathtt{u}$ 的字符串 $r$。你可以对 $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$ 变为可疑字符串。

说明/提示

在第一个测试点中，字符串 $\mathtt{sus}$ 已经是可疑字符串，因为 $\mathtt{s}$ 在串中出现了两次，并且唯一的 $\mathtt{u}$ 左右最近的 $\mathtt{s}$ 距离都为 $1$：$\color{red}{\mathtt{s}}\underline{\mathtt{u}}\color{red}{\mathtt{s}}$。

在第二个测试点中，最优操作方案是将第 $1$、$3$、$4$ 位改为 $\mathtt{s}$，此时字符串变为 $\mathtt{suss}$。此时 $\mathtt{suss}$ 是可疑字符串，因为 $\mathtt{s}$ 出现了 $3$ 次，并且唯一的 $\mathtt{u}$ 左右最近的 $\mathtt{s}$ 距离都为 $1$：$\color{red}{\mathtt{s}}\underline{\mathtt{u}}\color{red}{\mathtt{s}}\mathtt{s}$。

在第三个测试点中，由于字符串 $\mathtt{sssss}$ 没有 $\mathtt{u}$，条件对 $\mathtt{u}$ 的要求自然成立。所以原串已经是可疑字符串。

在第六个测试点中，最初的字符串 $\mathtt{usssssss}$ 并不是可疑字符串，因为唯一的 $\mathtt{u}$ 左右最近的两个 $\mathtt{s}$ 分别相距一格和两格：$\underline{\mathtt{u}}\color{red}{\mathtt{ss}}\mathtt{sssss}$。

由 ChatGPT 5 翻译

样例

9
sus
uuuu
sssss
uusuuu
suuuuuu
usssssss
sssuuusss
susuusuuus
uuuuuuuuuuu

0
3
0
3
3
1
1
2
6