时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
Doctor has a string s consisting of only lowercase letters. Doctor has got the set of all palindromic substrings of a string s, denoted by the set S. Now, he wants to choose two distinct strings a and b from the set S which satisfy that the string a is a substring of the string b. How many different pairs (a, b) can Doctor choose?
输入描述:
There are multiple test cases. The first line contains an integer T (), indicating the number of test cases. Test cases are given in the following.
Each test case consists of only one line, containing a non-empty string s (), consisting of only lowercase letters.
输出描述:
For each test case, output "Case #x: y" in one line (without quotes), where x indicates the case number starting from 1, and y denotes the answer to this test case.