Polycarp记性不好。他每天最多只能记住三个不同的字母。
Polycarp希望编写一个由小写英文字母组成的非空字符串，并希望在最少的天数里完成。请问他能在几天内做到这一点？
Polycarp最初有一个空字符串，只能在该字符串的末尾添加字符。
例如，如果Polycarp想写"lollipops"，他将在2天内完成：
第一天，Polycarp将记住字母l、o、i并写出 lolli；
第二天，Polycarp将记住字母p、o、s，将pops添加到生成的行中，从而完成整个字符串"lollipops"。
又如：如果Polycarp想写“stringology”，他将在4天内完成：
在第一天写str；
在第二天，将写 ing ；
第三天，编写olog；
第四天，写y。
Polycarp has a poor memory. Each day he can remember no more than 33 of different letters.
Polycarp wants to write a non-empty string of ss 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 22 days:
If Polycarp wants to write the string stringology, he will do it in 44 days:
For a given string ss, print the minimum number of days it will take Polycarp to write it.
The first line of input data contains a single integer tt (1≤t≤1041≤t≤104) — the number of test cases.
Each test case consists of a non-empty string ss consisting of lowercase Latin letters (the length of the string ss does not exceed 2⋅1052⋅105) — the string Polycarp wants to construct.
It is guaranteed that the sum of string lengths ss over all test cases does not exceed 2⋅1052⋅105.
For each test case, print a single number — minimum number of days it will take Polycarp to write the string ss from memory.
6
lollipops
stringology
abracadabra
codeforces
test
f
2
4
3
4
1
1