Palindromic Substrings Problem Statement

You are given a string 'STR'. Your task is to determine the total number of palindromic substrings present in 'STR'.

Example:

Input:

"abbc"

Output:

5

Explanation:

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

Constraints:

• 1 <= t <= 100
• 0 <= N <= 1000
• Where 't' is the number of test cases, 'N' is the length of 'STR'.
• Time Limit: 1 sec.

Note:

A palindrome reads the same forwards and backwards, such as "abba".

A substring is a contiguous sequence of characters within a string, such as "a", "b", "c", "ab", "bc", "abc" of "abc".

Input format:

The first line contains an integer 't' specifying the number of test cases or queries to be run. Each test case consists of a single string 'STR' for which you must count the palindromic substrings.

Output Format:

For each test case, return the total number of palindromic substrings. Output each result on a new line.