Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3807
Just a Palindrome

Time Limit: 2 Seconds      Memory Limit: 65536 KB

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".


Author: LIN, Xi
Source: ZOJ Monthly, August 2014
Submit    Status