Eloa’s Secret

rumman13 SUB Inter University Prog...
Limits 2s, 512 MB

Eloa, the princess of Byteland has a secret. She is obsessed with Alien names. The general convention of human name is “First name + Space + Last name”. There is one difference in alien name. The space replaced by a “:”. For example, “donald:trump” is a valid alien name. Obviously first name and last name can’t be empty. They must have at least one character each and only consists of lowercase English letters. Eloa has a long string S consists of lowercase English letters and “:”. She wants to know how many distinct sub-strings of S are there which can be considered as valid alien names. As she is very busy doing her makeup for the upcoming beauty contest, she ask you to do the task. Remember, you have to find the answer before she finishes her makeup. Otherwise the King of Byteland will hang you!

Input

Input starts with a positive integer T (1 ≤ T ≤ 1000), denoting the number of test cases. Each of the next T lines
contains a string S (1 ≤ |S| ≤ 50000). It is guaranteed that ∑|Si| ≤ 500000.

Output

For each test case, print the output in the format, “Case t: rt” (without the quotes) in a separate line. Here t is the case number starting from 1, and rt is the number of distinct alien names of tth test case.

Sample

InputOutput
4
a:b
abc
aa:ba:bb
a::b
Case 1: 1
Case 2: 0
Case 3: 7
Case 4: 0

Use scanf/printf for faster I/O.

Submit

Login to submit.

Statistics

100% Solution Ratio
ash_98Earliest, 2w ago
ash_98Fastest, 0.0s
salim_jnuLightest, 1.8 MB
ash_98Shortest, 2319B
Toph uses cookies. By continuing you agree to our Cookie Policy.