CF1702B Polycarp Writes a String from Memory

Polycarp 记忆力很差。每天他最多只能记住 $3$ 个不同的字母。 Polycarp 想要用最少的天数写出一个由小写拉丁字母组成的非空字符串 $s$。他需要多少天才能完成？ Polycarp 最开始有一个空字符串，只能在字符串末尾添加字符。 例如，如果 Polycarp 想要写出字符串 lollipops，他会用 $2$ 天完成： - 第一天，Polycarp 会记住字母 l、o、i，并写下 lolli； - 第二天，Polycarp 会记住字母 p、o、s，接着在已有字符串后添加 pops，最终得到 lollipops。 如果 Polycarp 想要写出字符串 stringology，他会用 $4$ 天完成： - 第一天写下部分 str； - 第二天写下部分 ing； - 第三天写下部分 olog； - 第四天写下部分 y。 对于给定的字符串 $s$，请输出 Polycarp 至少需要多少天才能将其写出。

输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例包含一个非空字符串 $s$，由小写拉丁字母组成（字符串 $s$ 的长度不超过 $2 \cdot 10^5$），表示 Polycarp 想要写出的字符串。 保证所有测试用例中字符串 $s$ 的总长度不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示 Polycarp 至少需要多少天才能将字符串 $s$ 从头到尾写出。

由 ChatGPT 4.1 翻译