404531: GYM101532 K Palindromes Building

An anagram is a word or phrase formed by rearranging the letters of another word or phrase, using all the original letters exactly once, such as "post", "stop", and "spot".

You are given a string s consisting of lowercase English letters. Your task is to count how many distinct anagrams of the string s are palindromes.

A palindrome is a word, phrase, number, or other sequence of characters which reads the same backward as forward, such as "madam" or "racecar".

For example, "aabb" has 6 distinct anagrams, which are: "aabb", "abab", "abba", "baab", "baba", "bbaa". Two of the previous anagrams are palindromes, which are: "abba", "baab".

The first line contains an integer T, where T is the number of test cases.

The first line of each test case contains an integer n (1 ≤ n ≤ 20), where n is the length of the string s.

The second line of each test contains a string s of length n consisting of lowercase English letters.

For each test case, print a single line containing how many distinct anagrams of the string s are palindromes.

5
4
aabb
6
ababbc
6
abaaba
12
babacbcbcaca
14
aaaabbcaaaabbc

2
0
3
90
105