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.