Now, you are given a string S. We want to know how many distinct substring of S which is palindrome.
输入解释
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.
输出解释
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.