Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Convert String into Palindrome

Limits 1s, 512 MB

A palindrome is a word, number, phrase, or other sequence of characters which reads the same backward as forward, such as “madam” or “racecar” or the number, “10801”. Sentence-length palindromes may be written when allowances are made for adjustments to capital letters, punctuation, and word dividers, such as “A man, a plan, a canal, Panama!”, “Was it a car or a cat I saw?” or “No ‘x’ in Nixon”. In this problem, you will be given a word which contains only lower alphabets. You need to find out a way to make the word palindrome by deleting minimum numbers of characters from the string. Let, a word of length n is “A1A2A3……An-2An-1An”. If you delete the ith character from the word then new word will be “A1A2A3….Ai-1Ai+1.…An-2An-1An”. Here is an example. Let, a word is “abbea”. Now, if you delete the 4th character ‘e’ from the word, you will get the word “abba”, which is a palindrome.

Input

The first line is an integer, T (T<=100), which is the number of test cases. This line is followed by T lines of T cases. Each case contains a word. The word contains only lower alphabets with no special characters. The length of the word is less than 1001.

Output

For each case, print the number of case following by the required result.

Samples

InputOutput
2
abxa
abdba
Case 1: 1
Case 2: 0

Look , For 1st case, if x is deleted from the word, then will we get the palindrome “aba”. For 2nd case, the word is already palindromic word, no character is required to delete.


Discussion