2.The Palidrome Island

Credits: 100

PROBLEM DESCRIPTION:

There is an island called popop. There was a craze for strange palindromic names in this island. One day a girl named lolol asked her elder brother momom what is the minimum number of transformations required to convert any string to a palindrome.The transformations permitted are as below

INPUT:

The input file contains several test cases. The first line of the input gives you the number of test cases, T (1=T=10). Then T test cases will follow, each in one line. The input for each test case consists of a string containing lower case letters only. You can safely assume that the length of this string will not exceed 1000 characters.

OUTPUT:

For each set of input print the test case number first. Then print the minimum number of characters needed to turn the given string into a palindrome.

SAMPLE INPUT:
3
madras
institute
technology

SAMPLE OUTPUT:
Case 1: 2
Case 2: 3
Case 3: 5