Count Distinct Palindromic Substrings

You are given a string and your task is to compute the number of distinct palindromic substrings within it. A palindrome is a string that reads the same forwards and backwards, and distinct substrings are counted only once.

For example, for the string \(ababa\), the distinct palindromic substrings are: \(a\), \(b\), \(aba\), \(bab\), and \(ababa\), giving a total of 5.

inputFormat

The first line contains an integer \(T\) representing the number of test cases. Each of the following \(T\) lines contains a single string \(s\).

outputFormat

For each test case, output a single line containing the number of distinct palindromic substrings in the given string.

1
ababa

5