All Submissions


A palindrome as you all know is a string that reads the same forward as well as backward.
In this problem you will be given a string which is to be converted into palindrome using the minimum number of
edit operations. The edit operation can be of four types:
1. you can insert any character at any position even at the beginning as well as at the end.
2. you can delete a character at any position.
3. you can replace a character by any other character.
4. you can interchange any two characters. These two characters may not be adjacent.
But, here is the twist. You can apply the first three operation any number of times but the last operation is to be applied just once.

So, you will be given this initial string and you have to print the minimal number of operations needed to make a palindrome from it.

Ahh, forgot this is Developer's CQM right. Sorry for inconvenience guys but the input for this problem won't be in the traditional format, rather you would be given input as XML document. The initial string will be specified inside the "" tag and there are multiple such tags. Beware apart from the tags that you see in the sample test cases there may be some junk tags like "Happy New year :) :)".

Input

An XML document as specified above with the initial string inside the tag.

Output

For each initial string print one line giving the minimal number of operations needed.

Constraints
Initial string will contain only lower-case english characters.
The size of the initial string will be less than or equal to 30.

Sample Input



abba


happy new year


dabba


babacvabba



Sample Output
0
1
2

Problem Setter: Dhruva Bhaswar
Problem Tester: Pushkar Anand

Languages: AWK,Bash,Brain,C#,JavaScript,Pascal,Perl,PHP,Python,Python3,Ruby,Text

Time Limit: 5 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Submit

Login to post clarification.

No Clarifications.

Contest

Mode Judge

Passive

Online

Overall Rankings

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0