Palindromic Substrings and Advantage

In this problem, you are given T test cases. For each test case, you are given a non-empty string. Your task is to compute the 'palindrome advantage' of the string, which is defined as the total number of palindromic substrings present in the string. A palindrome is a string that reads the same backward as forward. For example, the string 'ababa' has 9 palindromic substrings. You need to implement a solution that reads input from stdin and writes the result for each test case to stdout. Use efficient methods such as center expansion to count all palindromic substrings.

inputFormat

The first line of input contains an integer T (1 ≤ T ≤ 10^5) representing the number of test cases. Each of the following T lines contains a non-empty string composed of lowercase English letters.

outputFormat

For each test case, output a single line containing an integer that represents the total number of palindromic substrings in the corresponding input string.## sample

2
ababa
abc

9
3