There is a curious boy in Noapara village, his name is “MODON”.  He wrote a line of small letters only. Now, he want to know how many proper suffix is also prefix of that line. Proper suffix is a suffix of a text whose length is less than the original text. Now you have to help “MODON”. 

Input

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

Each case contains a string S where 1 ≤ length(S) ≤ 10⁶.

Output

 For each case, print the case number and the answer .

Example

Input:
3
ababab
aaaa
abcabc 
Output:
Case 1: 2
Case 2: 3
Case 3: 1