Wise cyt has got a string S with N (1 ≤ N ≤ 10^5 ) characters. All the characters of S are lowercase or uppercase  English letters. Now he challenges Xingxing to find out a string T of length N such that the length of the LCS (Longest Common Subsequence) of S and T is minimum. T also should be consisted of lowercase or uppercase English letters only. Now it is Xingxing’s problem to find out the string T. But you need to print the minimum length of such LCS given that Xingxing has found T correctly.

Input file starts with a single integer T (1 ≤ T ≤ 50), T test cases following. Each of the next T test cases has one string S on a line.

For each case print your output in format, ‘Case X: Y ’, on a single line where X denotes the case number starting from 1 and Y denotes the length of the shortest possible LCS.

Subsequence can be not constant.

RiseAbove