题目描述

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 翻译

样例

6
lollipops
stringology
abracadabra
codeforces
test
f

2
4
3
4
1
1