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

#ifdef LOCAL
#include "../debug.h"
#else
#define dbg(...)
#endif

namespace mint_ns {
template<auto P>
struct Modular {
    using value_type = decltype(P);
    value_type value;

    Modular(long long k = 0) : value(norm(k)) {}

    friend Modular<P>& operator += (      Modular<P>& n, const Modular<P>& m) { n.value += m.value; if (n.value >= P) n.value -= P; return n; }
    friend Modular<P>  operator +  (const Modular<P>& n, const Modular<P>& m) { Modular<P> r = n; return r += m; }

    friend Modular<P>& operator -= (      Modular<P>& n, const Modular<P>& m) { n.value -= m.value; if (n.value < 0)  n.value += P; return n; }
    friend Modular<P>  operator -  (const Modular<P>& n, const Modular<P>& m) { Modular<P> r = n; return r -= m; }
    friend Modular<P>  operator -  (const Modular<P>& n)                      { return Modular<P>(-n.value); }

    friend Modular<P>& operator *= (      Modular<P>& n, const Modular<P>& m) { n.value = n.value * 1ll * m.value % P; return n; }
    friend Modular<P>  operator *  (const Modular<P>& n, const Modular<P>& m) { Modular<P> r = n; return r *= m; }

    friend Modular<P>& operator /= (      Modular<P>& n, const Modular<P>& m) { return n *= m.inv(); }
    friend Modular<P>  operator /  (const Modular<P>& n, const Modular<P>& m) { Modular<P> r = n; return r /= m; }

    Modular<P>& operator ++ (   ) { return *this += 1; }
    Modular<P>& operator -- (   ) { return *this -= 1; }
    Modular<P>  operator ++ (int) { Modular<P> r = *this; *this += 1; return r; }
    Modular<P>  operator -- (int) { Modular<P> r = *this; *this -= 1; return r; }

    friend bool operator == (const Modular<P>& n, const Modular<P>& m) { return n.value == m.value; }
    friend bool operator != (const Modular<P>& n, const Modular<P>& m) { return n.value != m.value; }

    explicit    operator       int() const { return value; }
    explicit    operator      bool() const { return value; }
    explicit    operator long long() const { return value; }

    constexpr static value_type mod()      { return     P; }

    value_type norm(long long k) {
        if (!(-P <= k && k < P)) k %= P;
        if (k < 0) k += P;
        return k;
    }

    Modular<P> inv() const {
        value_type a = value, b = P, x = 0, y = 1;
        while (a != 0) { value_type k = b / a; b -= k * a; x -= k * y; swap(a, b); swap(x, y); }
        return Modular<P>(x);
    }

    friend void __print(Modular<P> v) {
        cerr << v.value;
    }
};
template<auto P> Modular<P> pow(Modular<P> m, long long p) {
    Modular<P> r(1);
    while (p) {
        if (p & 1) r *= m;
        m *= m;
        p >>= 1;
    }
    return r;
}

template<auto P> ostream& operator << (ostream& o, const Modular<P>& m) { return o << m.value; }
template<auto P> istream& operator >> (istream& i,       Modular<P>& m) { long long k; i >> k; m.value = m.norm(k); return i; }
template<auto P> string   to_string(const Modular<P>& m) { return to_string(m.value); }

}
constexpr int mod = 998244353;
using mod_int = mint_ns::Modular<mod>;

struct Comb {
    int n;
    vector<mod_int> _fac, _invfac, _inv;
    Comb() : n{0}, _fac{1}, _invfac{1}, _inv{0} {}
    Comb(int n) : Comb() { init(n); }
    void init(int m) {
        m = min(m, mod - 1);
        if (m <= n) return;
        _fac.resize(m + 1); _invfac.resize(m + 1); _inv.resize(m + 1);
        for (int i = n + 1; i <= m; i++) _fac[i] = _fac[i - 1] * i;
        _invfac[m] = _fac[m].inv();
        for (int i = m; i > n; i--) _invfac[i - 1] = _invfac[i] * i, _inv[i] = _invfac[i] * _fac[i - 1];
        n = m;
    }
    mod_int fac(int m) { if (m > n) init(2 * m); return _fac[m]; }
    mod_int invfac(int m) { if (m > n) init(2 * m); return _invfac[m]; }
    mod_int inv(int m) { if (m > n) init(2 * m); return _inv[m]; }
    mod_int ncr(int n, int r) { if (n < r || r < 0) return 0; return fac(n) * invfac(r) * invfac(n - r); }
  mod_int place(int n, int r) { return ncr(n + r - 1, r - 1); } // stars and bars : x1 + x2 - - - xr = n
} comb;


const int root = 62;
void ntt(vector<mod_int> &a) {
  int n = (int)a.size(), L = 31 - __builtin_clz(n);
  static vector<mod_int> rt(2, 1);
  for (static int k = 2, s = 2; k < n; k *= 2, s++) {
    rt.resize(n);
    mod_int z[] = {1, pow(mod_int(root), mod >> s)};
    for(int i = k ; i < 2 * k ; ++i)    rt[i] = rt[i / 2] * z[i & 1];
  }
  vector<int> rev(n);
  for(int i = 0 ; i < n ; ++i)  rev[i] = (rev[i / 2] | (i & 1) << L) / 2;
  for(int i  = 0 ; i < n ; ++i) if(i < rev[i])  swap(a[i], a[rev[i]]);

  for (int k = 1; k < n; k *= 2)
    for (int i = 0; i < n; i += 2 * k) for(int j = 0 ; j < k ; ++j) {
      mod_int z = rt[j + k] * a[i + j + k], &ai = a[i + j];
      a[i + j + k] = ai - z;
      ai += z;
    }
}

vector<mod_int> conv(const vector<mod_int> &a, const vector<mod_int> &b) {
  if (a.empty() || b.empty()) return {};
  int s = (int)a.size() + (int)b.size() - 1, B = 32 - __builtin_clz(s),
      n = 1 << B;
  mod_int inv = pow(mod_int(n), mod - 2);

  vector<mod_int> L(a), R(b), out(n);
  L.resize(n), R.resize(n);
  ntt(L), ntt(R);
  for(int i = 0 ; i < n ; ++i)
    out[-i & (n - 1)] = L[i] * R[i] * inv;
  ntt(out);
  return {out.begin(), out.begin() + s};
}

int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  auto __solve_testcase = [&](int test) {
    int N, M;  cin >> N >> M;

    int K = min(N, M);
    vector<mod_int> P(K + 1), T(K + 1);
    for(int i = 0 ; i <= K ; ++i) {
      P[i] = pow(mod_int(M - 1 - i), K) * comb.invfac(i);
      if(i & 1) P[i] *= -1;
      T[i] = comb.invfac(i);
    }


    vector<mod_int> res = conv(P, T);
    res.resize(K + 1);

    for(int i = 0 ; i <= K ; ++i)
      res[i] *= comb.fac(i);


    for(int i = M + 1 ; i <= N ; ++i) {
      vector<mod_int> nres(i + 1);
      mod_int pa = M;
      for(int j = i ; j >= 0 ; --j) {
        mod_int a = max(0, M - (i - j));
        mod_int b = M - pa;
        pa = a;
        if(j < i)
          nres[j] += b * res[j];
        if(j)
          nres[j] += a * res[j - 1];
      }
      swap(res, nres);
    }

    mod_int ans = 0;
    for(int i = 0 ; i <= N ; ++i)
      ans += res[i] * i;

    cout << ans << '\n';
  };

  int NumTest = 1;
  cin >> NumTest;
  for(int testno = 1; testno <= NumTest ; ++testno) {
    __solve_testcase(testno);
  }

  return 0;
}