#include<bits/stdc++.h>
#define file(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout)
using namespace std;
const int N=4010,p=998244353,inv2=p+1>>1;
int T,n,a[N],t[N],c[N];
int fac[N],ifac[N],h[N];
bitset<N> g[N],del;
int qpow(int x,int y=p-2){
	int m=1;
	for(;y;y>>=1,x=1ll*x*x%p)if(y&1)m=1ll*m*x%p;
	return m;
}
int C(int n,int m){
	return 1ll*fac[n]*ifac[m]%p*ifac[n-m]%p;
}
void init(int n){
	fac[0]=1;
	for(int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%p;
	ifac[n]=qpow(fac[n]);
	for(int i=n-1;i>=0;i--)ifac[i]=1ll*ifac[i+1]*(i+1)%p;
	for(int i=0;i<=n;i++){
		int mul=1;
		for(int j=0;j<=i;j+=2)h[i]=(h[i]+1ll*C(i,j)*mul%p)%p,mul=1ll*mul*(j+1)%p;
	}
}
void add(int &x,int y){x+=y;if(x>=p)x-=p;}
int calc(int n){
	int res=1;
	for(;;){
		int x=1;
		for(;x<=n;x++)if(!del[x])break;
		if(x>n)return res;
		int y=x+1;
		for(;y<=n;y++)if(!del[y]&&g[x][y])break;
		if(y>n){
			if(g[x][x])return 0;
			res=2ll*res%p;
			del[x]=1;
			continue;
		}
		for(int i=1;i<=n;i++)if(i!=x&&i!=y)g[i].reset(x),g[i].reset(y);
		del[x]=del[y]=1;res=2ll*res%p;
		g[x].reset(y),g[y].reset(x);
		if(g[x][x]){
			for(int i=1;i<=n;i++)if(i!=y&&g[y][i])g[i].flip(i);
		}
		if(g[y][y]){
			for(int i=1;i<=n;i++)if(i!=x&&g[x][i])g[i].flip(i);
		}
		if(g[x][x]&&g[y][y])res=p-res;
		g[x].reset(x),g[y].reset(y);
		for(int i=1;i<=n;i++)if(g[x][i])g[i]^=g[y];
		for(int i=1;i<=n;i++)if(g[y][i])g[i]^=g[x];
		for(int i=1;i<=n;i++)if(g[x][i]&&g[y][i])g[i].flip(i);
	}
}
signed main(){
//	file("match");
	scanf("%d",&T);
	init(N-10);
	for(;T--;){
		scanf("%d",&n);
		for(int i=1;i<=n;i++)c[i]=0;
		for(int i=1;i<=n;i++)scanf("%d",&a[i]),t[i]=a[i],c[a[i]]++;
		if(n==1){puts("1");continue;}
		int all=1,res=0;
		for(int i=1;i<=n;i++)all=1ll*all*h[c[i]]%p;
		sort(t+1,t+n+1);
		int m=unique(t+1,t+n+1)-t-1;
		for(int i=1;i<=n;i++)a[i]=lower_bound(t+1,t+m+1,a[i])-t;
		for(int i=1;i<=n+m;i++)g[i].reset(),del[i]=0;
		for(int i=1;i<=n;i++){
			g[i][n+a[i]]=g[n+a[i]][i]=1;
			for(int j=i+1;j<=n;j++)if(a[i]<a[j])g[i][j]=g[j][i]=1;
		}
//		printf("%d %d\n",f[0][0],f[0][1]);
		res=calc(n+m);
		res=1ll*res*qpow(inv2,m)%p;
//		printf("%d %d\n",all,res);
		printf("%lld\n",1ll*(res+all)*inv2%p);
	}
}