Counting Palindromic Substrings

Given a string \(s\), your task is to count the number of palindromic substrings contained in \(s\). A substring is a contiguous sequence of characters in the string, and a palindrome is a string that reads the same forwards and backwards (i.e. \(s = s^R\)).

For each test case, you will be given a string. Output the result in the exact format: Case #t: ans, where \(t\) is the test case number (starting from 1) and \(ans\) is the computed number of palindromic substrings.

You may use any correct algorithm. A common approach is to expand around potential centers.

inputFormat

The input is read from stdin and consists of:

1. A single integer \(T\) (\(1 \le T \le 100\)) representing the number of test cases.
2. \(T\) lines each containing a non-empty string \(s\) of lowercase English letters.

outputFormat

For each test case, output one line to stdout in the format:

Case #t: ans

where \(t\) is the test case number (starting from 1) and \(ans\) is the total count of palindromic substrings in the given string.

## sample

3
abba
racecar
palindrome

Case #1: 6
Case #2: 10
Case #3: 10

</p>