Kuo-chan can help send names to Mars.
However, he hates palindromes of length greater than 1. He gets upset whenever receiving a name containing palindrome substrings of length greater than 1.
We call a name's substring a palindrome if and only if it reads the same backwards and forwards. A string a is a substring of a string b if a can be obtained from b by deleting several (possibly zero or all) characters from the beginning and several (possibly zero or all) characters from the end.
For example,
Yang-chan also wants to send his name to Mars. However, as Kuo-chan's best friend, he doesn't want to upset Kuo-chan.
Therefore, Yang-chan will modify his name by replacing a letter at any position with any English letter. He can use this operation arbitrarily many times (possibly zero).
Yang-chan wants to know how many letters have to be modified at least?
(Please use C++ to solve this problem.)
The first and only line of the input contains a non-empty string S of lowercase English letters — Yang-chan's name.
The length of S will not exceed 105.
You should output a single integer, meaning the number of letters Yang-chan has to modify at least to avoid upsetting Kuo-chan.
Remember to add new line in the end