#include <bits/stdc++.h>
#define MAXN 5010
#define MOD 998244353
#define LL long long
#define For(i, a, b) for(int i = (a); i <= (b);i++)
#define Rof(i, a, b) for(int i = (a); i >= (b);i--)
using namespace std;
LL dp[MAXN][MAXN];
LL jc[MAXN],ny[MAXN],jcn[MAXN];
void INIT(){
    jc[0]=jc[1]=ny[1]=jcn[0]=jcn[1]=1;
    For(i,2,MAXN-1){
        jc[i]=jc[i-1]*i%MOD;
        ny[i]=(MOD-MOD/i)*ny[MOD%i]%MOD;
        jcn[i]=jcn[i-1]*ny[i]%MOD;
    }
}
LL C(int x,int y){
    if (y<0||y-x<0||x<0) return 0;
    return jc[y]*jcn[y-x]%MOD*jcn[x]%MOD;
}
int n,a[MAXN];
int num[MAXN],nt;
int sm[MAXN];
bool pf=0;
void Main(){
    nt=0;
    cin>>n;
    For(i,1,n){
        cin>>a[i];
        if (a[i]==a[i-1]) num[nt]++;
        else num[++nt]=1;
    }
    sm[nt+1]=0;
    Rof(i,nt,0) sm[i]=sm[i+1]+num[i];
    if (pf) For(i,0,nt) printf("sm[%d]=%d\n",i,sm[i]);
    if(num[nt]!=1){
        cout<<0<<"\n";
        return ;
    }
    For(i,0,n/2) dp[nt][i]=0;
    dp[nt][num[nt]]=1;
    For(i,0,nt-1) For(j,0,n/2) dp[i][j]=0;
    Rof(x,nt-1,1) For(y,0,min(sm[x],n/2)){
        For(i,0,1){
            if (pf) printf("dp[%d+1][%d-%d]=%d num[x]-i=%d 2*(y-i)-1-sm[x+1])=%d\n",x,y,i,dp[x+1][y-i],num[x]-i,2*(y-i)-(y-i!=n/2));
            dp[x][y]=(dp[x][y]+dp[x+1][y-i]*C(num[x]-i,2*(y-i)-(y-i!=n/2)-sm[x+1]))%MOD;
        }
        if (pf) printf("dp[%d][%d]=%d\n",x,y,dp[x][y]);
    }
    cout<<dp[1][n/2]<<"\n";
}
int main(){
    std::ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    INIT();
    int T;cin>>T;
    For(i,1,T) pf=0,Main();
}
/*
2
4
1 2 3 4
8
1 1 2 3 4 4 6 7
*/