#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int t, n, f[26], cnt;
ll fact[21], ans;
char s[21];
int main() {
fact[0] = 1;
for (int i = 1; i <= 20; ++i)
fact[i] = fact[i - 1] * i;
scanf("%d", &t);
while (t--) {
memset(f, 0, sizeof f);
scanf("%d%s", &n, s);
for (int i = 0; i < n; ++i)
++f[s[i] - 'a'];
cnt = 0;
for (int i = 0; i < 26; ++i)
if (f[i] & 1) ++cnt;
if (cnt > 1) puts("0");
else {
for (int i = 0; i < 26; ++i)
f[i] /= 2;
ans = fact[n / 2];
for (int i = 0; i < 26; ++i)
ans /= fact[f[i]];
printf("%lld\n", ans);
}
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnR5cGVkZWYgbG9uZyBsb25nIGxsOwp1c2luZyBuYW1lc3BhY2Ugc3RkOwppbnQgdCwgbiwgZlsyNl0sIGNudDsKbGwgZmFjdFsyMV0sIGFuczsKY2hhciBzWzIxXTsKaW50IG1haW4oKSB7CglmYWN0WzBdID0gMTsKCWZvciAoaW50IGkgPSAxOyBpIDw9IDIwOyArK2kpCgkJZmFjdFtpXSA9IGZhY3RbaSAtIDFdICogaTsKCXNjYW5mKCIlZCIsICZ0KTsKCXdoaWxlICh0LS0pIHsKCQltZW1zZXQoZiwgMCwgc2l6ZW9mIGYpOwoJCXNjYW5mKCIlZCVzIiwgJm4sIHMpOwoJCWZvciAoaW50IGkgPSAwOyBpIDwgbjsgKytpKQoJCQkrK2Zbc1tpXSAtICdhJ107CgkJY250ID0gMDsKCQlmb3IgKGludCBpID0gMDsgaSA8IDI2OyArK2kpCgkJCWlmIChmW2ldICYgMSkgKytjbnQ7CgkJaWYgKGNudCA+IDEpIHB1dHMoIjAiKTsKCQllbHNlIHsKCQkJZm9yIChpbnQgaSA9IDA7IGkgPCAyNjsgKytpKQoJCQkJZltpXSAvPSAyOwoJCQlhbnMgPSBmYWN0W24gLyAyXTsKCQkJZm9yIChpbnQgaSA9IDA7IGkgPCAyNjsgKytpKQoJCQkJYW5zIC89IGZhY3RbZltpXV07CgkJCXByaW50ZigiJWxsZFxuIiwgYW5zKTsKCQl9Cgl9CglyZXR1cm4gMDsKfQ==