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 <= 10⁶. 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)