← 返回题目列表

Codeforces · 1702/B

B. Polycarp 从内存中写入一个字符串

中文机器翻译题面 查看原题

波旅卡普的记忆力很差。每天他能记住的不同字母不超过 $$$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