#include <bits/stdc++.h>

using namespace std;

const int MAXN=2e3+50,P=998244353;
int N;
int a[MAXN];

long long f[MAXN][MAXN][2];

int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&N);
		for(int i=1;i<=N;i++)
		{
			scanf("%d",&a[i]);
		}
		for(int i=1;i<=N;i++)
		{
			for(int j=0;j<=N;j++)
			{
				f[i][j][0]=f[i][j][1]=0;
			}
		}
		f[0][0][0]=1;
		for(int i=1;i<=N;i++)
		{
			for(int j=0;j<=i;j++)
			{
				f[i][j][0]=(f[i-1][j][0]+1ll*((j+1-1)/2+1)*f[i-1][j+1][0]+1ll*(j+1)/2*f[i-1][j+1][1])%P;
				if(j>0)
				f[i][j][0]=(f[i][j][0]+f[i-1][j-1][0])%P;
				
				f[i][j][1]=(f[i-1][j][1]+1ll*((j+1-1)/2+1)*f[i-1][j+1][1]+1ll*(j+1)/2*f[i-1][j+1][0])%P;
				if(j>0)
				f[i][j][1]=(f[i][j][1]+f[i-1][j-1][1])%P;
		//		cout<<i<<" "<<j<<" "<<f[i][j][0]<<" "<<f[i][j][1]<<endl;
			}
		}
		printf("%lld\n",f[N][0][0]);	
	}
	
}