Wise owl has got a string S with N (1 ≤ N ≤ 105) characters. All the characters of S are lowercase English letters. Now she challenges Fallen 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 English letters only. Now it iss Fallen’s problem to find out the string T . But you ou need to print the minimum length of such LCS given that Fallen has found T correctly. Input 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. Output 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. Sample Input 2 ab efzadeuopqxrvwxaghijklmnbcastbqy Sample Output Case 1: 0 Case 2: 1