Orpheus, a well known artist, and artist intends to quiet Cerberus with his verse and securely stroll past him. He made an extremely unconventional sonnet for Cerberus. It comprises just of lowercase English letters. We consider a sonnet's substring a palindrome if
Correct answer will be upvoted else Multiple Downvoted. Computer science.
Orpheus, a well known artist, and artist intends to quiet Cerberus with his verse and securely stroll past him. He made an extremely unconventional sonnet for Cerberus. It comprises just of lowercase English letters.
We consider a sonnet's substring a palindrome if and provided that it peruses the equivalent in reverse and advances. A string a will be a substring of a string b if a can be acquired from b by erasing a few (conceivably zero or all) characters from the start and a few (perhaps zero or all) characters from the end.
Shockingly, Cerberus loathes palindromes of length more prominent than 1. For instance in the sonnet abaa the dog of Hades wouldn't care for substrings aba and aa.
Orpheus can possibly quiet Cerberus if the dog loves his verse. That is the reason he needs to change his sonnet so it doesn't contain any palindrome substrings of length more prominent than 1.
Orpheus can alter the sonnet by supplanting a letter at any situation with any lowercase English letter. He can utilize this activity discretionarily commonly (perhaps zero). Since there can be numerous palindromes in his sonnet, he might need to make a few amendments. Be that as it may, what number of, precisely? Given the sonnet, decide the insignificant number of letters that must be changed so the sonnet doesn't contain any palindromes of length more prominent than 1.
Input
The main line of the input contains a solitary integer t (1≤t≤105) signifying the number of experiments, then, at that point, t experiments follow.
The sole line of each experiment contains a non-void line of lowercase English letters, Orpheus' sonnet.
The amount of the length of Orpheus' sonnets in all experiments won't surpass 105.
Output
You should output t lines, I-th line ought to contain a solitary integer, reply to the I-th experiment.
Step by step
Solved in 4 steps with 1 images
