# tioj 1431 迴文數目

https://tioj.ck.tp.edu.tw/submissions/280900

* 計算各單字的數量，如果大於1個的單字數量是奇數，就不可能是迴文
* 每個單字個數除與一半（迴文兩邊各單字數量一定相同），並算一邊的排列數量
* 數量公式：$\dfrac{n!}{c_1!\times c_2!\times ...\times c_t!}$
* n：字串長度
* $c_i$：第i種單字數量
* t：單字種類數量

#include <bits/stdc++.h>
#define EB emplace_back
#define vci vector<int>
#define PII pair<int,int>
#define F first
#define S second
#define rep(a,b) for(int i=a;i<b;++i)
#define ALL(a) (a).begin(), (a).end()
#define SZ(a) (int)(a).size()
#define NL "\n"
#define LL long long
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

using namespace std;

LL fac[100];
int tail=2;

LL fact(int x){
    for(int i=tail;i<=x;++i){
        fac[i]=i*fac[i-1];
        tail++;
    }
    return fac[x];
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    fac[1]=1;

    while(n--){
        string str;
        cin>>str;
        int len=SZ(str);
        if(len==1){
            cout << 1 << NL;
            continue;
        }

        map<char,LL> cnt;
        rep(0,len)
            cnt[str[i]]++;

        LL cc=0;
        for(auto a=cnt.begin();a!=cnt.end();++a){
            if(a->second%2==1){
                cc++;
            }
        }
        // if more than one odd
        if(cc>1){
            cout << 0 << NL;
            continue;
        }

        LL tt=1;
        for(auto a=cnt.begin();a!=cnt.end();++a){
            if(a->second>1) tt*=fact(a->second/2);
        }
        cout << fact(len/2)/tt << NL;
    }
}