Palindrome Substrings

Given a string STR, your objective is to determine the total count of palindromic substrings within it.

Input:

The first line contains an integer 't', the number of test cases. Each subsequent line consists of a string 'STR'.

Output:

For each test case, output the total number of palindromic substrings of the given string on a new line.

Example:

If the input is:

abbc

The output should be:

5

Explanation: The palindromic substrings are ['a', 'b', 'b', 'c', 'bb'].

Constraints:

• 1 <= t <= 100
• 0 <= N <= 1000 where 'N' is the length of 'STR'.
• Time Limit: 1 sec.

Note:

A string is considered a palindrome if it reads the same forwards and backwards.