Count palindromes

Problem Statement

Count Palindromes You are given T test cases. In each test case, you are given an integer n and a string s of length n consisting only of lowercase English letters. Count the subsequences of s that can be rearranged to form a palindrome. Two subsequences are different when they use different positions of s , even if their resulting strings are equal. The empty subsequence is included. Because the answer may be very large, print its exact decimal representation. Input Format The first line contains an integer T . For each test case: The first line contains an integer n . The second line contains the string s . Output Format For each test case, print one line containing the exact count. Constraints 1 <= T <= 20 1 <= n <= 50,000 |s| = n s contains only lowercase English letters. The answer can contain more than 64 bits; do not use a fixed-width integer for the final answer. Examples Example 1 Input: 3 5 fihig 8 hhhghhih 6 gfihff Output: 10 128 20 For fihig , the valid subseque