#pragma optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long

const int mod=998244353;
int add(int x,int y){x+=y;return x>=mod?x-mod:x;}
int sub(int x,int y){x-=y;return x<0?x+mod:x;}
int mul(int x,int y){return (ll)x*y%mod;}
int ckmul(int &x,int y){x=mul(x,y);}
int ckadd(int &x,int y){x=add(x,y);}
int powmod(int x,int k){
    int ans=1;
    for(;k;k>>=1,x=mul(x,x))if(k&1)ans=mul(ans,x);
    return ans;
}
int inv(int x){return powmod(x,mod-2);}
int mul_inv(int x){return inv(x);}

void fft(int a[],int n,bool inv){
    for(int i=1,j=0;i<n;++i){
        int k=n;do j^=k>>=1;while(~j&k);
        if(j>i)swap(a[i],a[j]);
    }
    for(int j=2;j<=n;j<<=1){
        int ang=powmod(3,(mod-1)/j);
        if(inv)ang=mul_inv(ang);
        for(int i=0;i<n/j;++i){
            for(int k=i*j,cur=1;k<i*j+j/2;ckmul(cur,ang),++k){
                int tmp=mul(cur,a[k+j/2]);
                a[k+j/2]=sub(a[k],tmp);
                ckadd(a[k],tmp);
            }
        }
    }
    if(inv){
        int m=mul_inv(n);
        for(int i=0;i<n;i++)ckmul(a[i],m);
    }
}

const int N=1<<13;
vector<pair<int,int>> Qs[N];
int F[N],I[N];

int binom(int n,int k){
    return mul(F[n],mul(I[k],I[n-k]));
}

const int M=300050;
int ans[M];

void mul(int* a,int* b,int* c){
    fft(a,N*2,false);
    //fft(b,N*2,false);
    for(int i=0;i<N*2;i++)c[i]=mul(a[i],b[i]);
    fft(c,N*2,true);
    for(int i=N;i<N*2;i++)a[i]=0;
}

int dp[N],a[N*2],b[N*2],c[N*2];
//int bdp[N][N];
void Solve(){
    F[0]=1;
    for(int i=1;i<N;i++)F[i]=mul(F[i-1],i);
    I[0]=I[1]=1;
    for(int i=2;i<N;i++)I[i]=mul(mod-mod/i,I[mod%i]);
    for(int i=1;i<N;i++)I[i]=mul(I[i],I[i-1]);

    /*for(int m=1;m<N;m++){
        for(int n=1;n<N;n++){
            for(int x=1;x<=n;x++){
                bdp[m][n]=add(bdp[m][n],mul(add(bdp[m-1][n-x],1),mul(powmod(inv(m),n),mul(binom(n,x),powmod(m-1,n-x)))));
            }
            //printf("%i ",bdp[m][n]);
        }
        for(auto qu:Qs[m]){
            ans[qu.second]=bdp[m][qu.first];
        }
        //printf("\n");
    }*/
    //printf("\n");

    for(int n=0;n<N;n++){
        b[n]=I[n];
    }
    b[0]=0;
    fft(b,N*2,false);

    for(int i=0;i<N;i++)dp[i]=0;
    for(int m=1;m<N;m++){
        int now=1;
        for(int n=0;n<N;n++){
            a[n]=mul(add(dp[n],1),mul(I[n],now));
            now=mul(now,m-1);
        }
        mul(a,b,c);
        int in=inv(m);
        now=1;
        for(int n=0;n<N;n++){
            dp[n]=mul(c[n],mul(F[n],now));
            //if(n!=0)printf("%i ",dp[n]);
            now=mul(now,in);
        }
        //printf("\n");
        for(auto qu:Qs[m]){
            ans[qu.second]=dp[qu.first];
        }
    }
}

int main(){
    int t;
    scanf("%i",&t);
    for(int i=1;i<=t;i++){
        int n,m;
        scanf("%i %i",&n,&m);
        Qs[m].pb({n,i});
    }
    Solve();
    for(int i=1;i<=t;i++)printf("%i\n",ans[i]);
    return 0;
}