#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=4005,MOD=998244353,i2=(MOD+1)/2;
ll ksm(ll a,ll b=MOD-2,ll p=MOD) {
	ll ret=1;
	for(;b;a=a*a%p,b=b>>1) if(b&1) ret=ret*a%p;
	return ret;
}
ll dp[MAXN];
int cnt[MAXN],a[MAXN];
bitset <MAXN> adj[MAXN],f,g;
bool vis[MAXN];
ll calc(int n) {
	ll ans=1;
	for(int u=1;u<=n;++u) if(!vis[u]) {
		f.reset(),g.reset();
		int v=0;
		for(int i=u+1;i<=n;++i) if(!vis[i]&&adj[u][i]) {
			if(!v) v=i; f[i]=1;
		}
		cerr<<u<<" "<<v<<"\n";
		if(!v) {
			if(adj[u][u]) return 0;
			ans=ans*2%MOD; continue;
		}
		ans=ans*2%MOD,f[u]=f[v]=0;
		if(adj[v][v]) {
			if(adj[u][u]) ans=MOD-ans;
			for(int i=u+1;i<=n;++i) if(f[i]) adj[i].flip(i);
		}
		for(int i=u+1;i<=n;++i) if(adj[v][i]) {
			if(i!=v&&!vis[i]) g[i]=1;
			if(adj[v][i]&&adj[u][u]) adj[i].flip(i);
		}
		for(int i=1;i<=n;++i) if(!vis[i]) {
			if(f[i]&&g[i]) adj[i]^=f,adj[i]^=g,adj[i].flip(i);
			else if(f[i]) adj[i]^=g;
			else if(g[i]) adj[i]^=f;
		}
		vis[u]=vis[v]=true;
	}
	return ans;
}
void solve() {
	int n; scanf("%d",&n);
	for(int i=1;i<=n;++i) {
		scanf("%d",&a[i]),++cnt[a[i]];
		adj[a[i]+n][i]=adj[i][a[i]+n]=1;
	}
	for(int i=1;i<=n;++i) for(int j=i+1;j<=n;++j) if(a[i]<a[j]) {
		adj[i][j]=adj[j][i]=1;
	}
	ll ans=1;
	for(int i=1;i<=n;++i) ans=ans*dp[cnt[i]]%MOD;
	ans=(ans+calc(2*n)*ksm(i2,n))%MOD*i2%MOD;
	printf("%lld\n",ans);
	for(int i=1;i<=2*n;++i) adj[i].reset(),cnt[i]=a[i]=vis[i]=0;
	f.reset(),g.reset();
}
signed main() {
	dp[0]=dp[1]=1;
	for(int i=2;i<MAXN;++i) dp[i]=(dp[i-1]+dp[i-2]*(i-1))%MOD;
	int T; scanf("%d",&T);
	while(T--) solve();
	return 0;
}