Distinct Palindromic Substrings

You are given a string S along with its length N. Your task is to count the number of distinct palindromic substrings present in S.

A palindrome is a sequence of characters which reads the same backward as forward. For example, in the string "abba", the distinct palindromic substrings are "a", "b", "bb", and "abba".

The solution should process multiple test cases.

inputFormat

The first line contains an integer T, the number of test cases. Each test case consists of two lines. The first line contains an integer N, representing the length of the string S. The second line contains the string S.

outputFormat

For each test case, output a single line containing the number of distinct palindromic substrings in the given string S. (A palindrome is a string that reads the same backwards as forwards.)## sample

1
4
abba

4