Gyanbaba is the wisest saint of the universe. People from all over the world come to him to seek gyan (knowledge). But he does not offer his wisdom to everyone. He choses the right person to give wisdom after taking a test, his murids (apprentices) call this Gyanbaba's Admission Test. For the admission test Gyanbaba writes down a string containing lowercase English letters only and asks the applicants to find the substring of maximum length, the characters of which can be permuted to create a palindrome. Can you pass his test?

Input

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

Each case has a string S, the string Gyanbaba chose. You can assume 1≤length(S)≤100000.

Output

For each case print one line containing the case number starting with 1 and

the length of the substring, which satisfies Gyanbaba's query.

Example

Input:

2

abcfebcbbcbd

fesdddssefseefs

Output:

Case 1: 7

Case 2: 13