You want to create a certain target string , which consists only of lowercase English letters. You start with an empty string, and you are allowed to perform the following operations:
Add any single lowercase letter to the end of your string.
Copy any substring of your string (that is, all of the characters between some start point in your string and some end point in your string) to the clipboard. Doing this overwrites whatever was in the clipboard before. The clipboard starts off empty.
Add the entire contents of the clipboard to the end of your string. (The contents of the clipboard do not change.)
What is the smallest number of operations needed to create your target string? Note that you must create exactly the target string, with no additional letters.
输入格式
The first line of the input gives the number of test cases, . lines follow. Each line contains the target string .
输出格式
For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the minimum number of operations (as described in the problem statement) needed to create the target string.
样例
样例输入 1
3
abcabab
aaaaaaaaaaa
vnsdmvnsnsdmkvdmkvnsdmk
样例输出 1
Case #1: 6
Case #2: 7
Case #3: 15
数据范围与提示
The optimal solution for Sample Case is:
Type .
Type .
Type .
Copy to the clipboard.
Paste at the end of the string.
Paste at the end of the string.
The optimal solution for Sample Case is:
Type .
Type .
Type .
Copy to the clipboard.
Paste at the end of the string.
Copy to the clipboard.
Paste at the end of the string.
Limits
consists only of lowercase English letters in the range a through z.
