This problem is a Mooshak version of a UVA Online Judge Problem.

[PC029] String to Palindrome

In this problem you are asked to convert a string into a palindrome with minimum number of operations.

The operations are described below:

Here you'd have the ultimate freedom. You are allowed to:

• Add any character at any position
• Remove any character from any position
• Replace any character at any position with another character

Every operation you do on the string would count for a unit cost. You'd have to keep that as low as possible.<7p>

For example, to convert "abccda" you would need at least two operations if we allowed you only to add characters. But when you have the option to replace any character you can do it with only one operation. We hope you’d be able to use this feature to your advantage.

Input

The input file contains several test cases. The first line of the input gives you the number of test cases, \(t\).

Then \(t\) test cases will follow, each with a string \(s\)in one line. The string contains only lower case letters.

Output

For each test case print a line with he minimum number of characters needed to turn the given string into a palindrome.

Constraints

• \( 1 \leq t \leq 10 \)
• \( 1 \leq |s| \leq 1\,000 \)

6
tanbirahmed
shahriarmanzoor
monirulhasan
syedmonowarhossain
sadrulhabibchowdhury
mohammadsajjadhossain

5
7
6
8
8
8