当前没有测试数据。

题目描述

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 ($1 \leq T \leq 5$), 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 ($1 \leq |s| \leq 100000$), 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.

样例

样例输入 1

4
aaaa
abba
abacaba
abc

样例输出 1

Case #1: 6
Case #2: 4
Case #3: 14
Case #4: 0