题目描述

光头强的记忆力不太好。每天他最多只能记住 3 个不同的字母。（之前记住的都忘了）

光头强想要用最少的天数写出一个由小写拉丁字母组成的非空字符串 $s$。他能够在多少天内完成这个任务？

光头强最初有一个空字符串，只能在该字符串的末尾添加字符。

例如，如果光头强想要写出字符串 lollipops，他将在 $2$ 天内完成：

第一天，光头强将记住字母 l、o、i，然后写下 lolli； 第二天，光头强将记住字母 p、o、s，将它们添加到结果字符串末尾，得到字符串 lollipops。

如果光头强想要写出字符串 stringology，他将在 $4$ 天内完成：

第一天，写出 str； 第二天，写出 ing； 第三天，写出 olog； 第四天，写出 y。

对于给定的字符串 $s$，请输出光头强完成任务所需的最少天数。

输入格式

输入数据的第一行包含一个整数 $t(1≤t≤10^4)$ — 测试用例的数量。

每个测试用例由一个非空字符串 $s$ 组成，该字符串由小写拉丁字母组成 (字符串 $s$ 的长度不超过 $2⋅10^5$) — 光头强想要构造的字符串。

保证所有测试用例的字符串长度之和不超过 $2⋅10^5$。

输出格式

对于每个测试用例，请输出一个数字——光头强写出字符串 $s$ 的最小天数。

测试样例

6
lollipops
stringology
abracadabra
codeforces
test
f

2
4
3
4
1
1

样例说明