У Дмитрия есть строка \(s\), состоящая из строчных латинских букв.
Дмитрий решил удалить два подряд идущих символа из строки \(s\) и вам интересно, какое количество различных строк может получиться после такой операции.
Например, у Дмитрия есть строка «aaabcc». Вы можете получить следующие различные строки: «abcc»(при удалении первых двух или второго и третьего символов), «aacc»(при удалении третьего и четвёртого символов),«aaac»(при удалении четвертого и пятого символов) и «aaab»(при удалении последних двух).
Выходные данные
Для каждого набора входных данных выведите одно целое число — количество различных строк, которые можно получить, удалив две подряд идущие буквы.
Примечание
Первый пример разобран в условии.
В третьем примере получатся следующие строки: «cdef», «adef», «abef», «abcf», «abcd».
В седьмом примере при любом удалении получится строка «aba».
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
6
aaabcc
10
aaaaaaaaaa
6
abcdef
7
abacaba
6
cccfff
4
abba
5
ababa
|
4
1
5
3
3
3
1
|