波旅卡普的记忆力很差。每天他能记住的不同字母不超过 $$$3$$$。
Polycarp 想要写入一个由小写拉丁字母组成的 $$$s$$$ 非空字符串,需要最少的天数。他需要多少天才能做到?
Polycarp 最初有一个空字符串,只能在该字符串的末尾添加字符。
例如,如果Polycarp想要写字符串棒棒糖,他将在$$$2$$$天内完成:
- 第一天Polycarp会记住字母l、o、i并写出lolli;
- 第二天,Polycarp 会记住字母 p、o、s,将 pop 添加到结果行中并得到棒棒糖行。
如果波利卡普想写弦乐学,他会在 $$$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$$$ 所需的最少天数。
示例
输入 #1
6 lollipops stringology abracadabra codeforces test f
输出 #1
2 4 3 4 1 1