SUBPAL - Gyanbabas Admission Test

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

Added by:Sourav Sen Tonmoy
Date:2015-09-18
Time limit:5.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:Own problem. Used in University of Dhaka internal contest 2015, for 1st and 2nd year only.

hide comments
2015-09-18 18:05:42 Sourav Sen Tonmoy
Hi everyone! This is my first problem at SPOJ. I was facing a bit difficulty while adding it. And as a result the problem set and submission options were not available. Sorry for the temporary inconvenience. Thanks to good guy Robert Lewoń at SPOJ for helping me fixing the problems. Enjoy solving the problem.

Last edit: 2022-06-29 21:21:13
2015-09-18 17:50:39 Robert Lewon
Problem description will appear soon. Sorry for inconvenience.
2015-09-18 16:37:59 sairampola
no question ..
2015-09-18 14:25:12
unable to view question..
2015-09-18 12:11:41
where's the question ??
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.