CF1702B.Polycarp Writes a String from Memory

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.

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 写出它所需的最少天数。

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$.

输入数据的第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。

每个测试用例由一个非空字符串 $s$ 组成，该字符串仅包含小写拉丁字母（字符串 $s$ 的长度不超过 $2 \cdot 10^5$）—— 这是 Polycarp 希望构造的字符串。

保证所有测试用例中字符串 $s$ 的长度总和不超过 $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.

对于每个测试用例，输出一个整数——Polycarp 从记忆中写出字符串 $s$ 所需的最少天数。