PALINS - Nabid Loves Palindromic String

no tags 

Recently Nabid learn about palindromic string. A regular palindrome is a string of numbers or letters that is the same forward as backward. For example, the string "ABCDEDCBA" is a palindrome because it is the same when the string is read from left to right as when the string is read from right to left. Now when he finds a string he tries to make it into a palindromic string by changing character positions. It is simple for him when the string length is small. But not for a large string.

As you a Good Programmer Your task is to help Nabid.

Input

Input starts with an integer T (≤ 25), denoting the number of test cases.

Each case contains string S length L where 1 <= L <= 106. Assume that all the Characters are in uppercase (A-Z).

Output

For each case, print the case number and print YES or NO.

Example

Input:
3
BARID
AAFFG
JARIN

Output:
Case 1: NO
Case 2: YES
Case 3: NO

Problem Setter: Shipu Ahamed, Dept. of CSE
Bangladesh University of Business and Technology (BUBT)



Added by:Shipu Ahamed
Date:2013-06-29
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64