Just a Palindrome

Time Limit: 2 Seconds

Memory Limit: 65536 KB

Description

A palindrome is a symmetrical string, that is, a string read identically from left to right as well as from right to left.

There're a string s and an operation defined on the string.

  1. choose two integer i and j (1 ≤ i, j ≤ |s|).
  2. swap si and sj.

You are given the string, and you can perform the operation once. Please find the longest palindromic substring of string after you perform the operation.

Input

Input will consist of multiple test cases. Each test case contains exactly one line, which gives a non-empty string consisting of lowercase and uppercase letters. The length of the string will not be greater than 105.

Output

For each test case, print a line containing the test case number (beginning with 1) followed by the length of the longest palindrome.

Sample Input

aaabbacaa

Sample Output

Case 1: 8

Hint

The longest palindrom of string "aaabbacaa" is "abba". If we exchange the 'a' and 'c', we will get "aaabbaaac". The longest palindrom is "aaabbaaa".

Source

None

提交代码