#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1.5e6+10,LIM = 1.5e6,mod = 998244353;
int addv(int x,int y){return (x+y>=mod) ? (x+y-mod) : (x+y);}
int subv(int x,int y){return (x>=y) ? (x-y) : (x-y+mod);}
void add(int& x,int y){x = addv(x,y);}
void sub(int& x,int y){x = subv(x,y);}
int qpow(int a,int n){
    int res = 1;
    while(n){
        if(n&1)res = 1ll*res*a%mod;
        n>>=1; a = 1ll*a*a%mod;
    }
    return res;
}
int qinv(int a){return qpow(a,mod-2);}
//
void tomin(int& x,int y){x = min(x,y);} void tomax(int& x,int y){x = max(x,y);}
int fac[MAXN],rfac[MAXN],id,T;
int n,x[4],y[4],z[4],ans;

int la,ra,lb,rb,ls,rs;

int f[MAXN],g[MAXN],h[MAXN*2];

struct Poly{
    vector<int>a;
    int n;
    Poly(int N=0){a.resize(N+1,0);n=N;}
    void split(int N){if(n>N){a.resize(N+1,0);n=N;}}
};
namespace NTT{
	const int MAXN = 4e6+10;
    int f[MAXN],g[MAXN],h[MAXN],rev[MAXN],N;
    void change(int* f,int N){for(int i=0;i<N;i++)if(i<rev[i])swap(f[i],f[rev[i]]);}
    void DFT(int* f,int N,int rev){
        change(f,N);
        for(int len=2;len<=N;len<<=1){
            int step=qpow(rev,(mod-1)/len);
            for(int i=0;i<N;i+=len){
                int w=1;
                for(int j=0;j<len/2;j++){
                    int x=f[i+j],y=f[i+j+len/2];
                    f[i+j]=addv(x,1ll*w*y%mod);
                    f[i+j+len/2] = subv(x,1ll*w*y%mod);
                    w=1ll*w*step%mod;
                }
            }
        }
    }
    Poly ntt(Poly F,Poly G){
        int n=F.n,m=G.n;N=1;
        while(N<=(n+m))N<<=1;
        for(int i=0;i<N;i++)f[i]=g[i]=h[i]=0;
      	for(int i=0;i<N;i++){
            rev[i]=rev[i>>1]>>1;
            if(i&1)rev[i]|=(N>>1);
        }
       	for(int i=0;i<=n;i++)f[i]=F.a[i];
        for(int i=0;i<=m;i++)g[i]=G.a[i];
        DFT(f,N,3);DFT(g,N,3);
       	for(int i=0;i<N;i++)h[i]=1ll*f[i]*g[i]%mod;
        DFT(h,N,qinv(3));
        int inv=qinv(N);
       	for(int i=0;i<N;i++)h[i]=1ll*h[i]*inv%mod;
        Poly ret(n+m);
      	for(int i=0;i<=n+m;i++)ret.a[i]=h[i];
        return ret;
    }
};
Poly operator*(Poly p1,Poly p2){return NTT::ntt(p1,p2);}

void solve(){
    cin>>n; ans = 0;
    for(int i=1;i<=3;i++)cin>>x[i]>>y[i]>>z[i];
    //
    int D = y[3]-x[2]+x[1]+z[2]-z[3]-y[1];
    if(D%3)return void(cout<<"0\n");
    D /= 3;
    la = 0,ra = n,lb = 0,rb = n,ls = 0,rs = 2*n;

    tomin(rs,z[3]);
    tomax(lb,-D);
    tomin(rs,x[1]-D);
    tomax(la,-D+x[1]-x[2]);
    tomax(la,D+z[3]-z[2]);
    tomax(lb,x[1]+z[2]-x[3]-z[3]-2*D);
    tomin(rs,y[3]-x[2]+x[1]-2*D);

    if(la>ra || lb>rb || rs<0)return void(cout<<"0\n");

    for(int a=la;a<=ra;a++){
        int xy = a,zx = x[2]-x[1]+a+D,yz = z[2]-z[3]+a-D;
        f[a] = 1ll*rfac[xy]*rfac[zx]%mod*rfac[yz]%mod;
    }
    for(int b=lb;b<=rb;b++){    
        int yx = b,xz = b+D,zy = x[3]-x[1]-z[2]+z[3]+b+2*D;
        g[b] = 1ll*rfac[yx]*rfac[xz]%mod*rfac[zy]%mod;
    }
    Poly F(ra),G(rb);
    for(int i=la;i<=ra;i++)F.a[i] = f[i]; for(int i=lb;i<=rb;i++)G.a[i] = g[i];
    F = F*G;
    for(int s=0;s<=min(rs,ra+rb);s++)h[s] = F.a[s];
    for(int s=0;s<=rs;s++){
        int w = h[s];
        int zz = z[3]-s,xx = x[1]-s-D,yy = y[3]-x[2]+x[1]-s-2*D;
        w = 1ll*w*rfac[zz]%mod*rfac[xx]%mod*rfac[yy]%mod;
        add(ans,w);
    }

    //
    ans = 1ll*ans*fac[n]%mod;
    cout<<ans<<"\n";
}

int main(){
    //freopen("game.in","r",stdin); freopen("game.out","w",stdout);
    ios::sync_with_stdio(false); cin.tie(0);

    fac[0] = 1; for(int i=1;i<=LIM;i++)fac[i] = 1ll*fac[i-1]*i%mod;
    rfac[LIM] = qinv(fac[LIM]); for(int i=LIM-1;i>=0;i--)rfac[i] = 1ll*rfac[i+1]*(i+1)%mod;
    cin>>id>>T;
    while(T--)solve();

    return 0;
}