# 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 be “A1A2A3……An-2An-1An”. If you delete the ith character from the word then the new word will be “A1A2A3….Ai-1Ai+1.…An-2An-1An”. For example consider the word “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.

## Sample

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.

### Statistics

72% Solution Ratio

Mushfiq_4513Earliest, Sep '19

Abdullah_1234Fastest, 0.0s

omar24Lightest, 0 B

steinumShortest, 405B

### Related Contests

 Codeware19: Intra AUST Programming Contest Spring 2019Ended Aug '19 Replay of Codeware19: Intra AUST Programming Contest Spring 2019Ended Sep '19