У Поликарпа плохая память. Каждый день он может помнить не более \(3\) различных букв.
Поликарп хочет написать непустую строку \(s\), состоящую из строчных латинских букв, потратив на это минимальное количество дней. За сколько дней он справится?
Изначально Поликарп имеет пустую строку и может добавлять символы только в конец этой строки.
Например, если Поликарп хочет написать строку lollipops, то сделает это за \(2\) дня:
- в первый день Поликарп запомнит буквы l, o, i и напишет lolli;
- во второй день Поликарп запомнит буквы p, o, s, допишет к получившейся строке pops и получит строку lollipops.
Если Поликарп хочет написать строку stringology, то сделает это за \(4\) дня:
- в первый день будет написана часть str;
- во второй день будет написана часть ing;
- в третий день будет написана часть olog;
- в четвертый день будет написана часть y.
Для заданной строки \(s\) выведите минимальное количество дней, которое потребуется Поликарпу, чтобы написать ее.
Выходные данные
Для каждого набора входных данных выведите единственное число — минимальное количество дней, которое понадобится Поликарпу, чтобы написать по памяти строку \(s\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
lollipops
stringology
abracadabra
codeforces
test
f
|
2
4
3
4
1
1
|