考虑对每种方案，设其交点数为 \(t\)，我们就给答案加上 \((-1)^t\)。这样算出来的是偶 - 奇的方案数，加上总的方案数再除以二就是答案了。总的方案数可以简单算出，这里略过。
考虑一条边对奇偶性的贡献。发现如果这条边是 \((u,v)\) 其中 \(u<v\)，那么 \([u+1,v-1]\) 中有连边的点数的奇偶性就是这条边对奇偶性的贡献。
先考虑要求图时完美匹配的情况，考虑一种颜色，如果相邻两个点没有直接连接上，那么我们交换相邻两个点的匹配点后，一定会改变符号。并且可以发现这些总是一一对应的。所以只剩下唯一一种相邻点全部两两匹配的方案，这种方案的贡献为 \(1\)。
那多种颜色怎么办，还是考虑相邻点，我们考虑直接交换相邻点而不是它们的匹配点，那么总能交换成每种颜色单独成段的情况，且交换一次就改变一次符号。这个时候所有方案的权值和就都是 \(1\)。再算上前面的若干次交换，发现一个方案的 \((-1)^t\) 就是这个方案的 \(-1\) 的逆序对次方。
此时我们已经可以 DP 了，\(f(i,S,0/1)\) 表示考虑到前 \(i\) 个点，\(S\) 里面记录每种颜色的个数的奇偶性，\(0/1\) 表示逆序对奇偶性，可以做到 \(O(nA2^A)\)，其中 \(A\) 为颜色数。
现在考虑不是完美匹配的情况，那么相当于选出若干个点，且每种颜色选偶数个，要造成 \(-1\) 的逆序对次方的贡献。考虑建图，若 \(a_i>a_j\) 就连边 \((i,j)\)，那么就变成了 2nd ucup Stage 5. J 那个题。但是这样没保证每种颜色个数为偶数，考虑对每种颜色建一个主点连向每条边，这样这种颜色选奇数次的方案就消掉了。
那当然可以做到 \(O(\frac{n^3}{w})\)。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read(){
int x=0,f=1;char c=getchar();
for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
return x*f;
}
const int mod=998244353;
int ksm(int x,int y,int p=mod){
int ans=1;
for(int i=y;i;i>>=1,x=1ll*x*x%p)if(i&1)ans=1ll*ans*x%p;
return ans%p;
}
int inv(int x,int p=mod){return ksm(x,p-2,p)%p;}
mt19937 rnd(time(0));
int randint(int l,int r){return rnd()%(r-l+1)+l;}
void add(int &x,int v){x+=v;if(x>=mod)x-=mod;}
void Mod(int &x){if(x>=mod)x-=mod;}
const int N=4005;
bitset<N>G[N];
int n,a[N],f[2][2],g[2][2],F[N],cnt[N];
int fac[N],ifac[N];
void init(int V){
fac[0]=1;for(int i=1;i<=V;i++)fac[i]=1ll*fac[i-1]*i%mod;
ifac[V]=inv(fac[V])%mod;for(int i=V-1;i>=0;i--)ifac[i]=1ll*ifac[i+1]*(i+1)%mod;
}
int C(int x,int y){
if(x<y)return 0;
return 1ll*fac[x]*ifac[y]%mod*ifac[x-y]%mod;
}
void solve(){
n=read();
for(int i=1;i<=n;i++)cnt[a[i]=read()]++;
F[0]=1;for(int i=1;i<=n;i++)F[i]=1ll*F[i-1]*(2*i-1)%mod;
int A=1;
for(int i=1;i<=n;i++){
int cur=0;
for(int j=0;j*2<=cnt[i];j++)add(cur,1ll*F[j]*C(cnt[i],j*2)%mod);
A=1ll*A*cur%mod;
}
for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)if(a[i]>a[j])G[i].flip(j);
for(int i=1;i<=n;i++)G[n+a[i]].flip(i);
n<<=1;
for(int i=1;i<=n;i++){
// step 1
for(int j=i+1;j<=n;j++)if(G[i][j])G[j].flip(i),G[i][j]=0;
// step 2
int p=-1;
for(int j=i+1;j<=n;j++)if(G[j][i]!=0)p=j;
if(p==-1)continue;
swap(G[p],G[i+1]);
for(int j=i+1;j<=n;j++){
bool t=G[j][p];
G[j][p]=G[j][i+1],G[j][i+1]=t;
}
// step 3
bitset<N>f;f.reset();
for(int j=i+2;j<=n;j++)if(G[j][i])G[j]^=G[i+1],f[j]=1;
for(int j=i+1;j<=n;j++)if(G[j][i+1])G[j]^=f;
}
memset(f,0,sizeof(f)),memset(g,0,sizeof(g));
f[0][0]=1;
for(int i=1;i<=n;i++){
memset(g,0,sizeof(g));
for(int x=0;x<=1;x++)for(int y=0;y<=1;y++){
add(g[0][y],f[x][y]);
if(x==0)add(g[1][y^G[i][i]],f[x][y]);
else add(g[1][y^G[i][i]^G[i][i-1]],f[x][y]);
}
for(int x=0;x<=1;x++)for(int y=0;y<=1;y++)f[x][y]=g[x][y];
}
int ans=f[0][0];add(ans,f[1][0]);
ans=1ll*ans*2%mod;add(ans,mod-ksm(2,n));
ans=1ll*ans*inv(ksm(2,n>>1))%mod;
cout<<1ll*(ans+A)*inv(2)%mod<<endl;
for(int i=1;i<=n;i++)G[i].reset(),cnt[i]=0;
}
signed main(void){
init(N-5);
int tt=read();while(tt--)solve();
return 0;
}