Palindromic Substrings Problem Statement

Given a string STR, your task is to find the total number of palindromic substrings of STR.

Example:

Input:

STR = "abbc"

Output:

5

Explanation:

The palindromic substrings are ["a", "b", "b", "c", "bb"]. Therefore, the total count is 5.

Constraints:

• 1 ≤ t ≤ 100
• 0 ≤ N ≤ 1000
• where 't' is the number of test cases and 'N' is the length of the given string.
• Time Limit: 1 sec.

Note:

A string is a 'Palindrome' if it reads the same forwards and backwards (e.g., "abba"). A 'Substring' is a contiguous sequence of characters within a string.

Input:

The first line contains an integer 't' which denotes the number of test cases. Then, test cases follow. Each test case contains one string STR.

Output:

Return the total number of palindromic substrings possible. The output for each test case will be printed on a separate line.