{"problem":{"name":"K. Palindromes Building","description":{"content":"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 st","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10153K"},"statements":[{"statement_type":"Markdown","content":"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_\".\n\nYou 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.\n\nA _palindrome_ is a word, phrase, number, or other sequence of characters which reads the same backward as forward, such as \"_madam_\" or \"_racecar_\".\n\nFor 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_\".\n\nThe first line contains an integer T, where T is the number of test cases.\n\nThe first line of each test case contains an integer n (1 ≤ n ≤ 20), where n is the length of the string s.\n\nThe second line of each test contains a string s of length n consisting of lowercase English letters.\n\nFor each test case, print a single line containing how many distinct anagrams of the string s are palindromes.\n\n## Input\n\nThe 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.\n\n## Output\n\nFor each test case, print a single line containing how many distinct anagrams of the string s are palindromes.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T \\in \\mathbb{Z}^+ $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $:  \n- Let $ n_k \\in \\mathbb{Z} $, $ 1 \\leq n_k \\leq 20 $, be the length of string $ s_k $.  \n- Let $ s_k \\in \\Sigma^{n_k} $, where $ \\Sigma = \\{a, b, \\dots, z\\} $, be the input string.  \nLet $ f_k : \\Sigma \\to \\mathbb{Z}_{\\geq 0} $ denote the frequency count of each character in $ s_k $, i.e., $ f_k(c) = |\\{i : s_k[i] = c\\}| $.\n\n**Constraints**  \n1. $ 1 \\leq T \\leq \\text{unspecified (but finite)} $  \n2. For each $ k $: $ 1 \\leq n_k \\leq 20 $, and $ s_k $ consists only of lowercase English letters.\n\n**Objective**  \nFor each test case $ k $, compute the number of distinct palindromic anagrams of $ s_k $.  \n\nA string is a palindromic anagram of $ s_k $ if:  \n- It is a permutation of $ s_k $, and  \n- It reads the same forwards and backwards.  \n\nSuch a palindrome exists **iff** at most one character in $ s_k $ has odd frequency.  \nIf this condition holds, the number of distinct palindromic anagrams is:  \n$$\n\\frac{\\left( \\left\\lfloor \\frac{n_k}{2} \\right\\rfloor \\right)!}{\\prod_{c \\in \\Sigma} \\left( \\left\\lfloor \\frac{f_k(c)}{2} \\right\\rfloor \\right)!}\n$$  \nOtherwise, the count is $ 0 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10153K","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}