#include<bits/stdc++.h>
using namespace std;

#define int long long

using ll=long long;

using poly=vector<int>;

const int N=4e6+1e3+7,P=998244353,mod=P;

int qpow(int a,int b)
{
    int ret=1;
    while(b)
    {
        if(b&1)
            ret=ret*a%P;
        b>>=1;
        a=a*a%P;
    }
    return ret;
}

namespace Core {
    int a[N],b[N],w[N],rev[N];

    void NTT(int *a,int len)
    {
        for(int i=1;i<len;i++)
            if(i>rev[i])
                swap(a[i],a[rev[i]]);
        for(int d=1;d<len;d<<=1)
            for(int m=d<<1,i=0;i<len;i+=m)
                for(int j=0;j<d;j++)
                {
                    int x=a[i+j],y=a[i+j+d]*w[len/m*j]%P;
                    a[i+j]=(x+y>=P?x+y-P:x+y);
                    a[i+j+d]=(x-y<0?x-y+P:x-y);
                }
    }
}

int lastlen=-1;

poly operator *(const poly &va,const poly &vb)
{
    using namespace Core;
    int len=1;
    while(len<(int)va.size()+(int)vb.size()-1)
        len<<=1;
    for(int i=0;i<len;i++)
        a[i]=(i<(int)va.size()?va[i]:0);
    for(int i=0;i<len;i++)
        b[i]=(i<(int)vb.size()?vb[i]:0);
    if(lastlen!=len)
    {
        for(int i=1;i<len;i++)
            rev[i]=rev[i>>1]>>1|(i&1?len>>1:0);
        w[0]=1;
        w[1]=qpow(3,(P-1)/len);
        for(int i=2;i<len;i++)
            w[i]=1ll*w[i-1]*w[1]%P;
        lastlen=len;
    }
    NTT(a,len);
    NTT(b,len);
    for(int i=0;i<len;i++)
        a[i]=1ll*a[i]*b[i]%P;
    reverse(a+1,a+len);
    NTT(a,len);
    poly c(va.size()+vb.size()-1);
    for(int i=0,invlen=qpow(len,P-2);i<(int)c.size();i++)
        c[i]=a[i]*invlen%P;
    return c;
}

poly Fix(poly a,int n)
{
    a.resize(n);
    return a;
}

poly Inv(poly f,int n)
{
    poly g(1,qpow(f[0],P-2));
    while((int)g.size()<n)
    {
        int nlen=min<int>(g.size()<<1,n);
        poly tmp(Fix(Fix(f,nlen)*g,nlen));
        for(int i=0;i<nlen;i++)
            tmp[i]=(P-tmp[i]+(i==0?2:0))%P;
        g=Fix(g*tmp,nlen);
    }
    return g;
}

int k , p;
int t[N] , rt[N];

poly calc(int k,int p) {
    poly f(2) ; f[1] = 1;
    int ck = 1;
    for(int d = (int)__lg(k) - 1 ; d >= 0 ; d--) {
        ///
        poly g(f.size()) ;
        int l = g.size() - 1;
        int z = mod - ck;
        for(int i = 0, j = 1;i < g.size();i++, j = j * z % mod) g[l - i] = 1LL * rt[i] * j % mod;
        poly c = f * g;
        for(int i = 0;i <= ck ; i++) {
            c[i] = 1LL * c[i + l] * rt[i] % mod;
            f[i] = 1LL * f[i] * rt[i] % mod;
        }
        c.resize(ck + 1);
        f = f * c;

        ck *= 2;
        // for(int i = 0;i < f.size();i++) printf("%d ",f[i]) ; printf("\n");
        if((k >> d) & 1) {
            /// * (x - ck)
            f.push_back(0);
            for(int i = f.size() - 1;i >= 0;i--) {
                if(i) f[i] = (1LL * f[i] * (mod - ck) + f[i - 1]) % mod;
                else f[i] = 1LL * f[i] * (mod - ck) % mod;
            }
            ck++ ;
        }
        if(d) {
            for(int i = 0;i <= ck;i++) f[i] = 1LL * f[i] * t[i] % mod;
        }
    }
    // for(int i = 0;i < f.size();i++) printf("%d ",f[i]) ; printf("\n");

    // exit(0) ;
    poly ans(1) ; ans[0] = 1;
    bool ff = 0;
    while(p) {
        if(p & 1) {
            if(ff) ans = ans * f;
            else ans = f;
            ff = 1;

        }
        p >>= 1;
        if(p) f = f * f;
    }
    return ans;
}
int C(int a,int b) {
    return 1LL * t[a] * rt[b] %mod * rt[a - b] % mod;
}
void solv() {
    cin >> k >> p;
    poly p2 = calc(k , p);
    // for(int i = 0;i < p2.size();i++) printf("%d ",p2[i]) ;
    // printf("\n");
    int d = qpow(qpow(t[k] , mod - 2) , p) ;
    for(int i = 0;i < p2.size();i++) p2[i] = 1LL * p2[i] * d % mod;

    // poly F(k * p + 1) ;
    // F[0] = 1;
    // for(int i = 1;i <= k*p;i++) {
    //     for(int j = 0;j < i;j++) {
    //         int sol = 2LL * F[j] * C(i,j) % mod;
    //         if((i - j + 1) & 1) F[i] = (F[i] - sol + mod) % mod;
    //         else F[i] = (F[i] + sol) % mod;
    //     }
    // }
    // for(int i = 0;i <= k*p;i++) {
    //     F[i] = 1LL * F[i] * rt[i] % mod;
    //     printf("%d ",F[i]) ;
    // }
    // printf("\n") ;
    // exit(0) ;
    poly T(k * p + 1);
    T[0] = 0;
    for(int i = 1;i <= k*p;i++) {
        T[i] = rt[i] ;
        if((i + 1) & 1) T[i] = (mod - T[i]) % mod;
    }

    for(int i = 0;i <= k*p;i++) {
        T[i] = (2*T[i]) % mod ;
    }
    T[0] = (T[0] - 1 + mod) % mod;
    // poly K = F * T;
    // for(int i = 0;i <= k*p;i++) {
    //     printf("%d ",K[i] % mod) ; 
    // }
    // printf("\n");

    poly f = Inv(T , k*p + 1) ;
    // poly c = Fix(f * T, k * p  + 1);
    // for(int i = 0;i < c.size();i++) printf("%d ",c[i]) ; printf("\n");

    for(int i = 0;i < f.size();i++) {
        f[i] = 1LL * f[i] * (mod - 1) % mod;
        f[i] = 1LL * f[i] * t[i] % mod;
        // printf("%d ",f[i]);
    }
    // printf("\n");

    int ans = 0;
    for(int i = 0;i <= k * p;i++) {
        ans = (ans + 1LL * f[i] * p2[i]) % mod;
    }
    cout << ans << '\n';
}
signed main()
{
    ios::sync_with_stdio(false) ; cin.tie(0) ;
    int T;cin >> T;
    int N = 1e6;
    t[0] = rt[0] = 1;
    for(int i = 1 ; i <= N;i++) t[i] = 1LL * t[i - 1] * i % mod;
    rt[N] = qpow(t[N] , mod - 2);
    for(int i = N - 1;i >= 0;i--) rt[i] = 1LL * rt[i + 1] * (i + 1) % mod;

    while(T--) solv() ;
}