Sushant is learning about palindromes. One day his teacher gave him a string ‘STR’ consisting of only the lowercase letters and asked him to modify the string in such a way that the string doesn’t contain any palindromic substring by replacing the minimum characters present in the given string. Sushant, although a brilliant student, needs your help.
A palindrome is a word, number, phrase, or another sequence of characters that reads the same backward as forward, such as “madam” or “racecar”.
Given an ‘STR’: ‘aaaaaaa’ The minimum characters that will be replaced are 4. The string can be converted into ‘abcabca’.
Here are multiple possible answers, for example changing all the elements, but we have to find the minimum replacements possible.
The first line contains a single integer ‘T’ representing the number of test cases.
The first line of each test case will contain a string that represents the input string ‘STR’.
For each test case, print an integer denoting the minimum characters that can be replaced such that the string does not contain any palindromic substring of length 1.
Output for every test case will be printed in a separate line.
You don’t need to print anything; It has already been taken care of.
1 <= T <= 10^2
1 <= |STR| <= 10^3
Time Limit: 1 sec
Sample Input 1:
Sample Output 1:
Explanation For Sample Input 1:
In the first test case, the number of replaced characters is 0. As there are no substrings present in the given string, hence the answer is 0.
In the second test case, the number of replaced characters is 4. Here, the modified string can become abczaxqy
Sample Input 2:
Sample Output 2:
Explanation For Sample Input 2:
In the first test case, the number of replaced characters is 1. Here the string can be modified into racZcar
In the second test case, the number of replaced characters is 2. Here the string can be modified into plataoXnp