Convert String Into Palindrome

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

Input	Output
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.