Today is XllX's birthday. XllX wants to go to barbecue with his good friends. They go to a supermarket and get a lot of food. Then they ride to Laoyingzui, a good place to barbecue outside.
XllX thinks a perfect barbecue string must satisfy the property that it is in a format of abba(just like his name). That is, a perfect barbecue string s satisfies that si=si+3, si+1=si+2 (i≡1(mod4),len≡0(mod4) ), the index starts from 11 . Note that, empty string is a perfect string.
However, XllX is too busy to prepare the barbecue string. It might not be a perfect string. Now you can modify, add or delete one letter in 1 unit of time. Can you transfer the barbecue string into a perfect string in minimum unit of time?
Each test contains multiple test cases. The first line contains the number of test cases(1≤T≤12). Desc
Only one string stands for the barbecue string. It is guaranteed that the length of the string is not greater than 10^6106. All the letters of the string is in lowercase.
For each test case:
Print one integer in a line --- the minimum unit of time.
1
abbba1