由小写拉丁字母组成的字符串 $$$w$$$ 称为 可疑 当且仅当满足以下所有条件时:
- 字母 $$$\mathtt{s}$$$ 至少出现两次,并且
- 对于每次出现的字母 $$$\mathtt{u}$$$,最近出现的两个 $$$\mathtt{s}$$$ 距 $$$\mathtt{u}$$$ 的字符数相同。
在看到你完成一个字符串任务后,你的朋友 Aka 送给你一个字符串 $$$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$$$ 所需的最少操作数 可疑.
示例
输入复制
9susuuuusssssuusuuusuuuuuuussssssssssuuussssusuusuuusuuuuuuuuuuu
输出复制
030331126
注意
在第一个测试用例中,字符串 $$$\mathtt{sus}$$$ 已经是 可疑 因为 $$$\mathtt{s}$$$ 在字符串中出现了两次,并且距离唯一的 $$$\mathtt{u}$$$ 最近的两个 $$$\mathtt{s}$$$ 距离都为 $$$1$$$ 个字符: $$$\color{红色}{\mathtt{s}}\下划线{\mathtt{u}}\color{红色}{\mathtt{s}}$$$。
在第二个测试用例中,最好对索引 $$$1$$$、$$$3$$$ 和 $$$4$$$ 执行操作。之后,字符串 $$$s$$$ 变为 $$$\texttt{suss}$$$。字符串 $$$\mathtt{suss}$$$ 是 可疑 因为 $$$\mathtt{s}$$$ 在字符串中出现了 $$$3$$$ 次,并且距离唯一的 $$$\mathtt{u}$$$ 距离最近的两个 $$$\mathtt{s}$$$ 都相距 $$$1$$$ 个字符: $$$\color{红色}{\mathtt{s}}\下划线{\mathtt{u}}\color{红色}{\mathtt{s}}\mathtt{s}$$$。
在第三个测试用例中,$$$\mathtt{u}$$$ 的条件空为真,因为字符串 $$$\mathtt{sssss}$$$ 中没有 $$$\mathtt{u}$$$。因此,给定的字符串已经是 可疑.
在第六个测试用例中,初始字符串 $$$\mathtt{usssssss}$$$ 是 不 可疑 因为距离唯一的 $$$\mathtt{u}$$$ 最近的两个 $$$\mathtt{s}$$$ 分别相距一和两个字符:$$$\underline{\mathtt{u}}\color{red}{\mathtt{ss}}\mathtt{sssss}$$$。