#include<bits/stdc++.h>
#define R(i) for(i=1;i<=n;i++)
#define P long long
using namespace std;
const P N=4096,D=998244353,J=D/2+1;

P n,a[N],M,E,I[N],B[N],T,f[N],z,C,i,F,v,j;
bitset<N>G[N],V,S;

P e(P i,P j)
{
    return (i==j)?G[i][i]:G[i][j]^G[j][i];
}

void K(P u)
{
    if(u>n)return;
    if(B[u])return K(u+1);
    F=G[u][u],v=u;G[u][u]=0;
    M=M*2%D;
    while(!e(u,v)&&v<=n)v++;
    if(v>n)
    {
        if(F)M=0;
        return K(u+1);
    }
    G[u][v].flip();
    if(G[v][v])
    {
        R(i)if(e(u,i))G[i][i].flip();
        if(F)M*=-1;
    }
    V.reset();S.reset();
    R(i)V[i]=e(u,i),S[i]=e(v,i);
    R(i)if(S[i])
    {
        G[i]^=V;
        if(F)G[i][i].flip();
    }
    R(i)G[i][u]=G[i][v]=G[v][i]=G[u][i]=0;
    B[u]=B[v]=1;
    K(u+1);
}

main()
{
    cin>>T;
    f[0]=1;for(i=1;i<N;i++)f[i]=(f[i-1]+(i-1)*f[i-2]%D)%D;
    while(T--)
    {
        cin>>n;M=E=1;
        R(i)cin>>a[i];
        R(i)for(j=i+1;j<=n;j++)
        if(a[i]>a[j])G[i][j].flip();
        z=n;
        R(i)if(!I[a[i]])
        {
            ++z;C=0;I[a[i]]=1;
            for(j=i;j<=n;j++)if(a[i]==a[j])G[z][j].flip(),C++;
            M=M*J%D;E=E*f[C]%D;
        }
        n=z;
        K(1);
        cout<<(M+E+D)*J%D<<'\n';
        R(i)G[i].reset(),I[i]=B[i]=0;
    }
}