Polycarp Writes a String from Memory

题意翻译

可怜的 `Polycarp` 一天仅能记住三个不同的字母。过了这天这三个字母将被他忘记（这样才能为明天新记的三个字母腾出空间），因此他可能需要多天才能写完一个单词。 以单词 `stringology` 为例： ``` 第一天记住字母 s t r ，完成str； 第二天记住字母 i n g ，完成string； 第三天记住字母 o l g ，完成stringolog； 第四天记住字母 y ，完成整个单词stringology。 ``` 由于单词任务太多了， `Polycarp` 找到了聪明的你，你能告诉他每个单词他要花费多久才能写完吗？ **本题有多组数据** 第一行键入一个整数 $t$ （ $t$ 不超过 $10^4$ ），表示 `Polycarp` 要写完的单词总数。 以下每行一个字符串（保证字符串的长度不超过 $10^5$ ），表示他要完成的单词。 对于每个输入的字符串，输出一个整数 $ans$ ，表示他完成该单词需要花费的天数。

题目描述

Polycarp has a poor memory. Each day he can remember no more than $ 3 $ of different letters. Polycarp wants to write a non-empty string of $ s $ consisting of lowercase Latin letters, taking minimum number of days. In how many days will he be able to do it? Polycarp initially has an empty string and can only add characters to the end of that string. For example, if Polycarp wants to write the string lollipops, he will do it in $ 2 $ days: - on the first day Polycarp will memorize the letters l, o, i and write lolli; - On the second day Polycarp will remember the letters p, o, s, add pops to the resulting line and get the line lollipops. If Polycarp wants to write the string stringology, he will do it in $ 4 $ days: - in the first day will be written part str; - on day two will be written part ing; - on the third day, part of olog will be written; - on the fourth day, part of y will be written. For a given string $ s $ , print the minimum number of days it will take Polycarp to write it.

输入输出格式

输入格式

The first line of input data contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. Each test case consists of a non-empty string $ s $ consisting of lowercase Latin letters (the length of the string $ s $ does not exceed $ 2 \cdot 10^5 $ ) — the string Polycarp wants to construct. It is guaranteed that the sum of string lengths $ s $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

输出格式

For each test case, print a single number — minimum number of days it will take Polycarp to write the string $ s $ from memory.

输入输出样例

输入样例 #1

6
lollipops
stringology
abracadabra
codeforces
test
f

输出样例 #1

2
4
3
4
1
1

**题目大意：**
Polycarp的记忆力很差，每天只能记住不超过3个不同的字母。他想要写出一个由小写拉丁字母组成的非空字符串s，需要最少的天数。Polycarp最初有一个空字符串，只能向字符串的末尾添加字符。给定一个字符串s，输出Polycarp记住并写出该字符串所需的最少天数。

**输入输出数据格式：**
- **输入格式：**
第一行输入一个整数t（1≤t≤10^4），表示测试用例的数量。
每个测试用例包含一个由小写拉丁字母组成的非空字符串s（字符串s的长度不超过2×10^5）。
保证所有测试用例的字符串s长度之和不超过2×10^5。
- **输出格式：**
对于每个测试用例，输出一个数字——Polycarp记住并写出字符串s所需的最少天数。

**输入输出样例：**
- **输入样例：**
```
6
lollipops
stringology
abracadabra
codeforces
test
f
```
- **输出样例：**
```
2
4
3
4
1
1
```**题目大意：** Polycarp的记忆力很差，每天只能记住不超过3个不同的字母。他想要写出一个由小写拉丁字母组成的非空字符串s，需要最少的天数。Polycarp最初有一个空字符串，只能向字符串的末尾添加字符。给定一个字符串s，输出Polycarp记住并写出该字符串所需的最少天数。 **输入输出数据格式：** - **输入格式：** 第一行输入一个整数t（1≤t≤10^4），表示测试用例的数量。 每个测试用例包含一个由小写拉丁字母组成的非空字符串s（字符串s的长度不超过2×10^5）。 保证所有测试用例的字符串s长度之和不超过2×10^5。 - **输出格式：** 对于每个测试用例，输出一个数字——Polycarp记住并写出字符串s所需的最少天数。 **输入输出样例：** - **输入样例：** ``` 6 lollipops stringology abracadabra codeforces test f ``` - **输出样例：** ``` 2 4 3 4 1 1 ```