#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
template <typename T>inline void read(T &x)
{
    x=0;char c=getchar();bool f=0;
    for(;c<'0'||c>'9';c=getchar())f|=(c=='-');
    for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c-'0');
    x=(f?-x:x);
}
int n,m;
const int mod = 998244353;
int Pow(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1)res=1ll*res*a%mod;
        a=1ll*a*a%mod;
        b>>=1;
    }
    return res;
}
const int N = 5050;
int C[N][N],f[N],pw[N];
int bi[N][N],inv[N],ifac[N],fac[N];
void solve()
{
    read(n);read(m);
    LL inf=1e18;
    if(m<=30)inf=(1ll<<m);m=Pow(2,m);
    f[1]=1;pw[0]=1;f[0]=1;
    for(int i=1;i<=2*n;i++)pw[i]=1ll*pw[i-1]*m%mod;
    inv[1]=1;
    for(int i=2;i<=n;i++)inv[i]=1ll*inv[mod%i]*(mod-mod/i)%mod;
    ifac[0]=fac[0]=1;
    for(int i=1;i<=n;i++)
    {
        ifac[i]=1ll*ifac[i-1]*inv[i]%mod;
        fac[i]=1ll*fac[i-1]*i%mod;
    }
    for(int d=0;d<=2*n;d++)
    for(int i=0;i<=2*n;i++)
    {
        bi[d][i]=1;
        for(int j=0;j<i;j++)
        bi[d][i]=1ll*bi[d][i]*(m-d-j+mod)%mod;
    }
    for(int i=2;i<=2*n;i++)
    {
        f[i]=(bi[0][i-1]-1ll*f[i-2]*(i-1)%mod*(m-(i-2)+mod)%mod+mod)%mod;
    }
    int ans=0;
    for(int i=0;i<=n;i++)
    for(int j=0;j<=i;j++)
    if(2*i-j+n-i<=m)
    {
        int ret=1ll*C[n][i]*C[i][j]%mod*C[i][j]%mod*fac[j]%mod;
        ret=1ll*ret*f[2*i-2*j]%mod*bi[2*i-2*j][n-i+j]%mod;
        if((n-i)&1)ret=mod-ret;
        ans=(ans+ret)%mod;
        //cout<<i<<' '<<j<<' '<<ret<<' '<<f[2*i-2*j]<<' '<<bi[2*i-2*j][n-(2*i-2*j)]<<endl;
    }
    printf("%d\n",ans);
}
int main()
{
    int T;
    read(T);
    C[0][0]=1;
    for(int i=1;i<N;i++)
    {
        C[i][0]=1;
        for(int j=1;j<=i;j++)
        C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
    }
    while(T--)
    {
        solve();
    }
	return 0;
}
/*
3
3 3 3
1 3
3 2
1 2
1 1
2 2 3
3 1 2 3
3 3 3
1 3
3 2
1 2
1 1
2 2 3
3 1 2 3
3 3 3
1 3
3 2
1 2
1 1
2 2 3
3 1 2 3
*/