Problem2213--Number

2213: Number

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

Please solve the following problem:
Given a string s, suppose another string r is chosen randomly from all different substrings of s with equal probability, what is the expected number of occurrence of r in s?
For example, if s =“aab”, there are 5 substrings namely “a”, “b”, “aa”, “ab”, “aab”, thus the answer is (2 + 1 + 1 + 1 + 1)/5 = 6/5.

Input

There are several test cases.
For each test case, there is a single line containing a string of Latin letters whose whose length will never exceed 200.
Input is terminated by EOF.

Output

For each test case, output one line “Case X: Y” where X is the test case number (starting from 1) and Y is a real number representing the answer.
A result within absolute error of 10

Sample Input Copy

aab

Sample Output Copy

Case 1: 1.20000