Problem Description

Now, you are given a string S. We want to know how many distinct substring of S which is palindrome.

Input

The first line of the input contains a single integer T(T<=20), which indicates number of test cases.
Each test case consists of a string S, whose length is less than 100000 and only contains lowercase letters.

Output

For every test case, you should output "Case #k:" first in a single line, where k indicates the case number and starts at 1. Then output the number of distinct substring of S which is palindrome.

3
aaaa
abab
abcd

Case #1: 4
Case #2: 4
Case #3: 4