#include <bits/stdc++.h>

using namespace std;
mt19937 rnd;
#define app push_back
#define all(x) (x).begin(),(x).end()
#ifdef LOCAL
#define debug(...) [](auto...a){ ((cout << a << ' '), ...) << endl;}(#__VA_ARGS__, ":", __VA_ARGS__)
#define debugv(v) do {cout<< #v <<" : {"; for(int izxc=0;izxc<v.size();++izxc) {cout << v[izxc];if(izxc+1!=v.size()) cout << ","; }cout <<"}"<< endl;} while(0)
#else
#define debug(...)
#define debugv(v)
#endif
#define lob(a,x) lower_bound(all(a),x)
#define upb(a,x) upper_bound(all(a),x)
const int MOD = 998244353;
const long long MOD2 = (long long) MOD * MOD;
const int root = 3;
const int alim = 64; // Bound for using O(n^2) polynomial mult

int modpow(int b, int e) {
	int ans = 1;
	for (; e; b = (long long) b * b % MOD, e /= 2)
		if (e & 1) ans = (long long) ans * b % MOD;
	return ans;
}

const int MODinv = 2 - MOD; // pow(-MOD, -1, 2**32)
inline int m_reduce(long long x) {
  int m = x * MODinv;
  return (x>>32) - (((long long) m * MOD) >> 32);
}

const int r2 = modpow(2, 64);
inline int m_transform(int x) {
  return m_reduce((long long)x * r2);
}

inline int m_add(int x, int y) {
  int z = x + y;
  return z < 0 ? z + MOD : z - MOD;
}

inline int m_sub(int x, int y) {
  int z = x - y;
  return z < 0 ? z + MOD : z - MOD;
}

inline int m_mult(int x, int y) {
  return m_reduce((long long) x * y);
}

vector<int> rt = {1};
vector<int> transformed_rt;
vector<int> transformed_rt2;

template<int a>
void transform(vector<int> &P) {
  int m = P.size();
  int n = m / a;

  int size = rt.size();
  while (2 * size < n) {
    rt.resize(n / 2);
    int r = modpow(root, MOD / (4 * size));
    for (int i = 0; i < size; ++i)
      rt[i + size] = (long long) r * rt[i] % MOD;
    size *= 2;
  }

  // For montgomery
  for (int i = transformed_rt.size(); i < rt.size(); ++i) {
    transformed_rt.resize(rt.size());
    transformed_rt[i] = m_transform(rt[i]);
    transformed_rt2.resize(rt.size());
    transformed_rt2[i] = (unsigned int) MODinv * transformed_rt[i];
  }

  int k = n;
  while (k >= 4) k /= 4;

  if (k == 2) {
    int step = n * a;
    int half_step = step / 2;
    for (int j1 = 0; j1 < half_step; ++j1) {
      int j2 = j1 + half_step;

      int diff = m_sub(P[j1], P[j2]);
      P[j1] = m_add(P[j1], P[j2]);
      P[j2] = diff;
    }
    k = n/2;
  } else {
    k = n;
  }

  for (; k > 1; k /= 4) {
    for (int i = 0; i < n/k; ++i) {
      int step = k * a;
      int half_step = step / 2;
      int quarter_step = half_step / 2;

      int R20  = transformed_rt2[2 * i];
      int RR0 = transformed_rt[2 * i];

      int R21 = transformed_rt2[2 * i + 1];
      int RR1 = transformed_rt[2 * i + 1];

      int R2 = transformed_rt2[i];
      int RR = transformed_rt[i];

      int j1 = i * step;
      int j2 = j1 + quarter_step;
      int j3 = j2 + quarter_step;
      int j4 = j3 + quarter_step;

      for (int j = 0; j < quarter_step; ++j, ++j1, ++j2, ++j3, ++j4) {
        int z0;
        {
          int z = P[j3];
          int m = (unsigned int) R2 * z;
          z0 = ((long long) z * RR - (long long) m * MOD) >> 32;
        }

        int z1;
        {
          int z = P[j4];
          int m = (unsigned int) R2 * z;
          z1 = ((long long) z * RR - (long long) m * MOD) >> 32;
        }

        int sum0 = m_add(P[j1], z0);
        int diff0 = m_sub(P[j1], z0);
        int sum1 = P[j2] + z1;
        int diff1 = P[j2] - z1;

        // [sum0, sum1, diff0, diff1]

        int zz0;
        {
          int z = sum1;
          int m = (unsigned int) R20 * z;
          zz0 = ((long long) z * RR0 - (long long) m * MOD) >> 32;
        }

        int zz1;
        {
          int z = diff1;
          int m = (unsigned int) R21 * z;
          zz1 = ((long long) z * RR1 - (long long) m * MOD) >> 32;
        }

        P[j1]  = m_add(sum0, zz0);
        P[j2]  = m_sub(sum0, zz0);
        P[j3]  = m_add(diff0, zz1);
        P[j4]  = m_sub(diff0, zz1);
      }
    }
  }

  for (int i = 0; i < m; ++i)
    if (P[i] < 0) P[i] += MOD;
}

template<int a>
void inverse_transform(vector<int> &P) {
  int m = P.size();
  int n = m / a;
  int n_inv = m_transform(modpow(n, MOD - 2));

  vector<int> rev(n);
  for (int i = 1; i < n; ++i) {
    rev[i] = rev[i / 2] / 2 + (i & 1) * n / 2;
  }

  // P = [p * n_inv for p in P]
  for (int i = 0; i < m; ++i)
    P[i] = m_mult(n_inv, P[i]);

  // P = [P[a * rev[i // a] + (i % a)] for i in range(m)]
  for (int i = 1; i < n; ++i)
    if (i < rev[i])
      swap_ranges(P.begin() + a * i, P.begin() + a * i + a, P.begin() + a * rev[i]);

  // P = [P[-a * (i // a) + (i % a)] for i in range(m)]
  for (int i = 1; i < n/2; ++i)
    swap_ranges(P.begin() + a * i, P.begin() + a * i + a, P.begin() + a * (n - i));

  transform<a>(P);

  // P = [P[a * rev[i // a] + (i % a)] for i in range(m)]
  for (int i = 1; i < n; ++i)
    if (i < rev[i])
      swap_ranges(P.begin() + a * i, P.begin() + a * i + a, P.begin() + a * rev[i]);
}

template<int a>
void fast_polymult_mod(vector<int> &P, vector<int> &Q) {
  int m = P.size();
  int n = m / a;

  transform<a>(P);
  transform<a>(Q);

  vector<int> &PQ = P;
  for (int i = 0; i < n; ++i) {
    vector<unsigned long long> res(2 * a);
    for (int j = 0; j < a; ++j) {
      if (j >= 10 && j % 9 == 8)
        for (int k = j; k < j + a - 10; ++k)
          res[k] -= (res[k] >> 63) * 9 * MOD2;
      for (int k = 0; k < a; ++k)
        res[j + k] += (long long) P[i * a + j] * Q[i * a + k];
    }

    int c = rt[i/2];
    if (i & 1) c = MOD - c;
    for (int j = 0; j < a; ++j)
      PQ[i * a + j] = (res[j] + c * (res[j + a] % MOD)) % MOD;
  }

  inverse_transform<a>(PQ);
}

template <size_t... N>
void work(std::index_sequence<N...>, int x, std::vector<int>& a, std::vector<int>& b) {
  static void (*ptrs[])(std::vector<int>&, std::vector<int>&) = {&fast_polymult_mod<N+1>...};
  ptrs[x - 1](a, b);
}

void fast_polymult(vector<int> &P, vector<int> &Q) {
  int m1 = P.size();
  int m2 = Q.size();
  int res_len = m1 + m2 - 1;

  int b = 1;
  while ((alim << b) < res_len) ++b;
  int a = ((res_len - 1) >> b) + 1;
  int m = a << b;

  P.resize(m);
  Q.resize(m);

  // Call fast_polymult_mod<a>(P, Q);
  work(std::make_index_sequence<alim>{}, a, P, Q);

  P.resize(res_len);
}
vector<int> operator *(vector<int> v1,vector<int> v2)
{
  fast_polymult(v1,v2);
  return v1;
}
const int p=998244353;
int po(int a,int b) {if(b==0) return 1; if(b==1) return a; if(b%2==0) {int u=po(a,b/2);return (u*1LL*u)%p;} else {int u=po(a,b-1);return (a*1LL*u)%p;}}
int inv(int x) {return po(x,p-2);}
const int B=2005;
const int maxn=2*B;
int f[B][B];
int fact[maxn];int invf[maxn];
vector<int> rev(vector<int> A)
{
    int n=A.size();
    vector<int> v1(n),v2(n+1);
    for(int i=0;i<n;++i) {v1[i]=(A[i]*1LL*fact[i])%p;}
    for(int diff=0;diff<n;++diff) {v2[n-diff]=(diff%2==0 ? invf[diff] : (p-invf[diff])%p);}
    vector<int> v3=v1*v2;
    vector<int> B(n);
    for(int i=0;i<n;++i)
    {
        B[i]=(v3[n+i]*1LL*invf[i])%p;
    }
    return B;
}
vector<int> rev2(vector<int> A)
{
    int n=A.size();
    vector<int> v1(n),v2(n+1);
    for(int i=0;i<n;++i) {v1[i]=(A[i]*1LL*fact[i])%p;}
    for(int diff=0;diff<n;++diff) {v2[n-diff]=(invf[diff]);}
    vector<int> v3=v1*v2;
    vector<int> B(n);
    for(int i=0;i<n;++i)
    {
        B[i]=(v3[n+i]*1LL*invf[i])%p;
    }
    return B;
}
int h[maxn][maxn];int Q[maxn][maxn];
int res[maxn][maxn];
int C[maxn][maxn];
int32_t main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    for(int i=0;i<maxn;++i)
    {
        for(int j=0;j<=i;++j)
        {
            if(j==0 || j==i) {C[i][j]=1;continue;}
            C[i][j]=C[i-1][j]+C[i-1][j-1];if(C[i][j]>=p) C[i][j]-=p;
        }
    }
    fact[0]=1; for(int i=1;i<maxn;++i) {fact[i]=(fact[i-1]*1LL*i)%p;} for(int i=0;i<maxn;++i) {invf[i]=inv(fact[i]);}
    f[0][0]=1;
    for(int d=B-1;d>=1;--d)
    {
        for(int nx=B-1;nx>=0;--nx)
        {
            for(int nz=(B-1)/d;nz>=0;--nz)
            {
                if(nx+d+1<B && nz+1<B)
                {
                    f[nx+d+1][nz+1]-=f[nx][nz];if(f[nx+d+1][nz+1]<0) f[nx+d+1][nz+1]+=p;
                }
            }
        }
        vector<int> AA,BB;
        for(int nx=0;nx<B-d;++nx)
        {
            AA.clear();BB.clear();
            int deg=(B-1)/d;
            for(int i=0;i<deg;++i)
            {
                AA.app(f[nx][i]);
            }
            while(!AA.empty() && AA.back()==0) {AA.pop_back();}
            if(AA.empty()) continue;
            BB=rev(AA);
            for(int i=0;i<BB.size();++i)
            {
                if(i+d<B && nx+d<B)
                {
                    h[nx+d][i+d]+=BB[i];if(h[nx+d][i+d]>=p) h[nx+d][i+d]-=p;
                }
                if(i+d-1<B && nx+d<B)
                {
                    h[nx+d][i+d-1]-=BB[i];if(h[nx+d][i+d-1]<0) h[nx+d][i+d-1]+=p;
                }
            }
        }
    }
    vector<int> AA,BB;
    for(int nx=0;nx<B;++nx)
    {
        AA.clear();BB.clear();
        int deg=B;
        for(int i=0;i<deg;++i)
        {
            AA.app(h[nx][i]);
        }
        while(!AA.empty() && AA.back()==0) {AA.pop_back();}
        if(AA.empty()) continue;
        BB=rev2(AA);
        for(int i=0;i<BB.size();++i)
        {
            h[nx][i]=BB[i];
        }
    }
    Q[0][0]=1;
    for(int d=B-1;d>=1;--d)
    {
        for(int nx=0;nx<B-d;++nx)
        {
            for(int nz=(B-1)/d;nz>=0;--nz)
            {
                if(nx+d<B && nz+1<B)
                {
                    Q[nx+d][nz+1]+=Q[nx][nz];if(Q[nx+d][nz+1]>=p) Q[nx+d][nz+1]-=p;
                }
            }
        }
    }
    vector<int> h1(2*B*B),Q1(2*B*B);
    for(int i=0;i<B;++i)
    {
        for(int j=0;j<B;++j)
        {
            h1[2*B*i+j]=h[i][j];
            Q1[2*B*i+j]=Q[i][j];
        }
    }
    //vector<int> h2(B*B),h3(B*B),Q2(B*B),Q3(B*B);
    //for(int i=0;i<B*B;++i) {h2[i]=h1[i];h3[i]=h1[i+B*B];Q2[i]=Q1[i];Q3[i]=Q1[i+B*B];}
    vector<int> res1=h1*Q1;
    for(int i=0;i<B;++i)
    {
        for(int j=0;j<B;++j)
        {
            int el=2*i*B+j;
            res[i][j]=res1[el];
        }
    }
    int t;cin>>t;
    while(t--)
    {
        int n,m;cin>>n>>m;
        int answ=0;
        for(int d=1;d<=n;++d)
        {
            answ+=(res[m][d]*1LL*C[n-1][d-1])%p;if(answ>=p) answ-=p;
        }
        cout<<answ<<'\n';
    }
    return 0;
}