#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxm=5000,maxn=maxm/2,MOD=998244353;

int te,n,m,a[maxm+5],cnt[maxm+5],sum[maxm+5];
int INV[maxm+5],fac[maxm+5];
int f[maxm+5][maxn+5][2];

#define ADD(x,y) (((x)+(y))%MOD)
#define MUL(x,y) ((LL)(x)*(y)%MOD)
void Make(int n){
	INV[0]=INV[1]=1;for (int i=2;i<=n;i++) INV[i]=MUL(MOD-MOD/i,INV[MOD%i]);
	fac[0]=1;for (int i=1;i<=n;i++) fac[i]=MUL(fac[i-1],i),INV[i]=MUL(INV[i-1],INV[i]);
}
inline int C(int x,int y){
	if (y==0) return 1;
	return x<y?0:MUL(fac[x],MUL(INV[y],INV[x-y]));
}
int main(){
	Make(maxm);
	for (scanf("%d",&te);te;te--){
		scanf("%d",&m);n=m/2;
		for (int i=m;i;i--) scanf("%d",&a[i]);
		int tem=m;m=0;
		for (int i=1,j;i<=tem;i=j){
			for (j=i;j<=tem && a[i]==a[j];j++);
			a[++m]=a[i];cnt[m]=j-i;sum[m]=sum[m-1]+cnt[m];
		}
		for (int i=1;i<=m;i++)
			for (int j=1;j<=n;j++)
				f[i][j][0]=f[i][j][1]=0;
		f[0][0][0]=1;
		for (int i=1;i<=m;i++)
			for (int j=0;j<=i && j<=n;j++){
				f[i][j][0]=ADD(f[i][j][0],MUL(ADD(f[i-1][j][0],f[i-1][j][1]),C(j-1+(j==n)-(sum[i-1]-j),cnt[i])));
				if (j) f[i][j][1]=ADD(f[i][j][1],MUL(ADD(f[i-1][j-1][0],f[i-1][j-1][1]),C(j-2-(sum[i-1]-(j-1)),cnt[i]-1)));
			}
//		for (int i=1;i<=m;i++)
//			for (int j=1;j<=n;j++)
//				printf("f[%d][%d][0]=%d f[%d][%d][1]=%d\n",i,j,f[i][j][0],i,j,f[i][j][1]);
		printf("%d\n",ADD(f[m][n][0],f[m][n][1]));
	}
	return 0;
}