You are provided with a string consisting of only Latin letter (a-z). You need to find the no. of subsequences which are palindromes such that all the subsequences of the palindromic subsequence are palindromes themselves.
Helpful Links:
https://en.wikipedia.org/wiki/Palindrome
https://en.wikipedia.org/wiki/Subsequence
Input:
First Line contains T: no. of test cases
Each Test case consists of 2 lines. The first line contains the length of the string.
The second line contains the string.
OUTPUT:
Only a single line containing the no. of subsequences fulfilling the above conditions.
Constraints:
T<100
For string S
1<=|S|<=50
in the first substring, valid subsequences are "p","a","n","i","k", so answer=5
in the second string, valid subsequences are "j","a","v","a","aa", so answer=5
