#include <bits/stdc++.h>
using namespace std;
const int B = 45 ;
const int mod = 998244353;
typedef long long ll;
int f[2][2005][2005];
const int N = 2000;
int g[2][2005][2005];
int h[2][2005][2005];
int G[4100][4100];
int F[4100][4100];
int cur , cur2 , curh;

inline int inc(int x,int y){return x+y>=mod?x+y-mod:x+y;}
inline int dec(int x,int y){return x-y<0?x-y+mod:x-y;}
inline int mul(int x,int y){return (ll)x*y%mod;}
inline int qpow(int x,int y){
	int res=1;
	for(;y;y>>=1)res=y&1?mul(res,x):res,x=mul(x,x);
	return res;
}
inline int inv(int x){return qpow(x,mod-2);}

const int Nl=1<<12;
namespace NTT{
    int re[Nl],w[2][Nl];
    inline int getre(int n){
        int len=1,bit=0;
        while(len<n)len<<=1,++bit;
        for(int i=1;i<len;++i)re[i]=(re[i>>1]>>1)|((i&1)<<(bit-1));
        w[0][0]=w[1][0]=1,w[0][1]=qpow(3,(mod-1)/len),w[1][1]=inv(w[0][1]);
        for(int o=0;o<2;++o)for(int i=2;i<len;++i)
            w[o][i]=mul(w[o][i-1],w[o][1]);
        return len;
    }
    inline void NTT(int* a,int n,int o=0){
        for(int i=1;i<n;++i)if(i<re[i])swap(a[i],a[re[i]]);
        int R;
        for(int k=1;k<n;k<<=1)
            for(int i=0,t=k<<1,st=n/t;i<n;i+=t)
                for(int j=0,nw=0;j<k;++j,nw+=st)
                    R=mul(a[i+j+k],w[o][nw]),a[i+j+k]=dec(a[i+j],R),a[i+j]=inc(a[i+j],R);
        if(o){
            R=inv(n);
            for(int i=0;i<n;++i)a[i]=mul(a[i],R);
        }
    }
}
void REV(int f[][4100] ) {
    for(int i = 0;i < 4096;i++) {
        for(int j = 0;j < i;j++) swap(f[i][j] , f[j][i]) ;
    }
    return ;
}
void DFT(int f[][4100] , int o = 0) {
    if(o) REV(f) ;
    for(int i = 0;i < 4096;i++){
        NTT::NTT(f[i] , 4096 , o) ;
    }
    REV(f) ;
    for(int i = 0;i < 4096;i++) {
        NTT::NTT(f[i] , 4096 , o) ;
    }
    if(!o) REV(f) ;
    return ;
}
void init() {
    NTT::getre(N * 2) ;
    DFT(F);
    DFT(G);
    for(int i = 0;i < (1 << 12) ; i++) {
        for(int j = 0;j < (1<<12) ; j++) {
            F[i][j] = 1LL * F[i][j] * G[i][j] % mod;
        }
    }
    DFT(F , 1) ;
}
void solv() {
    int n , m;
    cin >> n >> m;
    int ans = h[curh][n][m]; /// max < B
    ans = (ans + F[n][m]) % mod;
    
    cout << ans << '\n';
    return ;
}
int main() {
    ios::sync_with_stdio(false) ; cin.tie(0) ;
    cur = 1;
    f[0][0][0] = 1;
    for(int i = 1;i < B;i++) {
        memset(f[cur] , 0 ,sizeof(f[cur]));
        for(int j = 0 ; j <= N ; j++) {
            for(int k = 0;k <= N;k++) {
                f[cur][j][k] = f[cur ^ 1][j][k] ;
                if(j >= 1) {
                    f[cur][j][k] = (f[cur][j][k] + f[cur][j - 1][k]) % mod;
                    if(k >= i) f[cur][j][k] = (f[cur][j][k] + f[cur][j - 1][k - i]) % mod;
                }
            }
        }
        cur ^= 1;
    }
    cur ^= 1;
    for(int i = 0;i <= N;i++) for(int j = 0;j <= N;j++) F[i][j] = f[cur][i][j];

    g[0][0][0] = 1;
    cur2 = 1;
    for(int i = 1 ; i <= N/B ; i++) {
        memset(g[cur2] , 0 , sizeof(g[cur2])) ;
        for(int j = 0;j <= N;j++) {
            for(int k = 0;k <= N;k++) {
                if(j >= 1) {
                // insert fake, the first one must be true
                    if(k)
                        g[cur2][j][k] = g[cur2][j - 1][k];
                /// insert true
                    if(k >= B) {
                        g[cur2][j][k] = (g[cur2 ^ 1][j - 1][k - B] + g[cur2][j][k]) % mod;
                    }
                }
                /// add 1
                if(k >= i)
                    g[cur2][j][k] = (g[cur2][j][k] + g[cur2][j][k - i]) % mod;
                G[j][k] = (G[j][k] + g[cur2][j][k]) % mod;
            }
        }
        cur2 ^= 1;
        // printf("%d %d\n",i,mnv);

    }
    cur2 ^= 1;

    curh = 1;
    h[0][0][0] = 1;
    for(int i = B - 1;i >= 1;i--) {
        memset(h[curh] , 0 ,sizeof(h[curh]));
        for(int j = 0 ; j <= N ; j++) {
            for(int k = 0;k <= N;k++) {
                h[curh][j][k] = h[curh ^ 1][j][k] ;
                if(j >= 1) {
                    if(k)
                        h[curh][j][k] = (h[curh][j][k] + h[curh][j - 1][k]) % mod;
                    if(k >= i) h[curh][j][k] = (h[curh][j][k] + h[curh][j - 1][k - i]) % mod;
                }
            }
        }
        curh ^= 1;
    }
    curh ^= 1;

    /// > B

    init() ;
    int t;cin >> t;
    while(t--) solv() ;
}