B. Поликарп пишет строку по памяти
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Поликарпа плохая память. Каждый день он может помнить не более $$$3$$$ различных букв.

Поликарп хочет написать непустую строку $$$s$$$, состоящую из строчных латинских букв, потратив на это минимальное количество дней. За сколько дней он справится?

Изначально Поликарп имеет пустую строку и может добавлять символы только в конец этой строки.

Например, если Поликарп хочет написать строку lollipops, то сделает это за $$$2$$$ дня:

  • в первый день Поликарп запомнит буквы l, o, i и напишет lolli;
  • во второй день Поликарп запомнит буквы p, o, s, допишет к получившейся строке pops и получит строку lollipops.

Если Поликарп хочет написать строку stringology, то сделает это за $$$4$$$ дня:

  • в первый день будет написана часть str;
  • во второй день будет написана часть ing;
  • в третий день будет написана часть olog;
  • в четвертый день будет написана часть y.

Для заданной строки $$$s$$$ выведите минимальное количество дней, которое потребуется Поликарпу, чтобы написать ее.

Входные данные

В первой строке входных данных записано единственное целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Каждый набор входных данных состоит из непустой строки $$$s$$$, состоящей из строчных латинских букв (длина строки $$$s$$$ не превышает $$$2 \cdot 10^5$$$) — строка, которую хочет построить Поликарп.

Гарантируется, что сумма длин строк $$$s$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите единственное число — минимальное количество дней, которое понадобится Поликарпу, чтобы написать по памяти строку $$$s$$$.

Пример
Входные данные
6
lollipops
stringology
abracadabra
codeforces
test
f
Выходные данные
2
4
3
4
1
1