Problem Description

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 $s_i=s_{i+3}$, $s_{i+1}=s_{i+2}$ ( $i \equiv 1 \pmod 4$, $len \equiv 0 \pmod 4$ ), the index starts from $1$ . 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?

Input

Each test contains multiple test cases. The first line contains the number of test cases $(1 \le T \le 12)$. Description of the test cases follows.

Only one string stands for the barbecue string. It is guaranteed that the length of the string is not greater than $10^6$. All the letters of the string is in lowercase.

Output

For each test case:

Print one integer in a line --- the minimum unit of time.

1
abbba

1