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.
1168: Water Problem: LCS时间限制: 2 Sec 内存限制: 128 MB
提交: 143 解决: 47
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.
2 ab abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ
Case 1: 0 Case 2: 1
Subsequence can be not constant.