/**
 * @file N.cpp
 * @author georgeyucjr ([email protected])
 * @brief
 * @version 998244353.1145141919810
 * @date 2024-04-19
 *
 * @copyright Copyright (c) 2024
 *
 */
# include <bits/stdc++.h>

# ifndef ONLINE_JUDGE
# define LOCAL
# endif

# if __cplusplus >= 201100LL
# else
# error Please use C++11 Or Higher CPP version
# endif

using ll = long long;
using ull = unsigned long long;
using i128 = __int128;
using u128 = unsigned __int128;
using arr3 = std :: array < int, 3 >;
using arr4 = std :: array < int, 4 >;
using pii = std :: pair < int, int >;

# if __cplusplus >= 201400LL
# define rep(i, f, t, ...) for ( std :: decay < decltype ( f + t ) > :: type i = f, _END_##i = t, ##__VA_ARGS__; i <= _END_##i; ++i )
# define per(i, f, t, ...) for ( std :: decay < decltype ( f + t ) > :: type i = f, _END_##i = t, ##__VA_ARGS__; i >= _END_##i; --i )
# else
# define rep(i, f, t, ...) for ( decltype ( f + t ) i = f, _END_##i = t, ##__VA_ARGS__; i <= _END_##i; ++i )
# define per(i, f, t, ...) for ( decltype ( f + t ) i = f, _END_##i = t, ##__VA_ARGS__; i >= _END_##i; --i )
# endif

# define emb emplace_back
# define pb push_back
# define mkp make_pair
# define FILEIO(filename) freopen(filename ".in", "r", stdin), freopen(filename ".out", "w", stdout)

# ifndef INLINE_V
# if __cplusplus >= 201700LL
# define INLINE_V inline
# else
# define INLINE_V
# endif
# endif

# if __cplusplus >= 201400LL
# define EXPR constexpr
# else
# define EXPR
# endif

# if __cplusplus >= 201400LL

template < class T, class U >
inline constexpr auto ceil ( T && x, U && y ) {
  return ( x > 0 ? ( x + y - 1 ) / y : x / y );
}

template < class T, class U >
inline constexpr auto floor ( T && x, U && y ) {
  return ( x > 0 ? x / y : ( x - y + 1 ) / y );
}

template < class T, class U >
inline constexpr auto divmod ( T && x, U && y ) {
  auto && q = floor ( x, y );
  return std :: pair { q, x - q * y };
}

inline constexpr auto sqr ( const auto & x ) { return x * x; }
inline constexpr auto Max ( const auto & x ) { return x; }
inline constexpr auto Min ( const auto & x ) { return x; }
inline constexpr auto Max ( const auto & x, const auto & y, const auto & ... args ) { return x < y ? Max ( y, args ... ) : Max ( x, args ... ); }
inline constexpr auto Min ( const auto & x, const auto & y, const auto & ... args ) { return x < y ? Min ( x, args ... ) : Min ( y, args ... ); }
inline constexpr void chkmax ( auto & d, const auto & ... x ) { d = Max ( d, x ... ); }
inline constexpr void chkmin ( auto & d, const auto & ... x ) { d = Min ( d, x ... ); }

# else

template < class T, class U >
inline T ceil ( T && x, U && y ) {
  return ( x > 0 ? ( x + y - 1 ) / y : x / y );
}

template < class T, class U >
inline T floor ( T && x, U && y ) {
  return ( x > 0 ? x / y : ( x - y + 1 ) / y );
}

template < class T, class U >
inline pair < T, T > divmod ( T && x, U && y ) {
  T && q = floor ( x, y );
  return std :: make_pair ( q, x - q * y );
}

template < class T >
inline T sqr ( const T & x ) { return x * x; }

template < class T, class ... Args >
inline T Max ( const T & x, const T & y, const Args & ... args ) {
  return x < y ? Max ( y, args ... ) : Max ( x, args ... );
}

template < class T, class ... Args >
inline T Min ( const T & x, const T & y, const Args & ... args ) {
  return x > y ? Min ( y, args ... ) : Min ( x, args ... );
}

template < class T, class ... Args >
inline T chkmax ( T & d, const Args & ... x ) { d = Max ( d, x ... ); }

template < class T, class ... Args >
inline T chkmin ( T & d, const Args & ... x ) { d = Min ( d, x ... ); }

# endif

# define ALL(vc) std :: begin ( vc ), std :: end ( vc )

# if __cplusplus >= 202000LL

template < class T >
requires ( std :: is_signed_v < T > || std :: is_unsigned_v < T > )
INLINE_V constexpr static T inf = std :: numeric_limits < T > :: max ( ) >> 1;

template <std :: ranges :: forward_range R>
inline constexpr auto Sum ( R && r ) {
  return std :: accumulate ( std :: ranges :: begin ( r ), std :: ranges :: end ( r ), 0 );
}

template < std :: ranges :: forward_range R, typename T >
inline constexpr auto Sum ( R && r, T init) {
  return std :: accumulate ( std :: ranges :: begin ( r ), std :: ranges :: end ( r ), init );
}

template < std :: ranges :: forward_range R >
inline constexpr int SZ ( R && x ) { return std :: size ( x ); }

# else

template < class R >
inline EXPR auto Sum ( R && r ) {
  return std :: accumulate ( ALL ( r ), 0);
}

template < class R, typename T >
inline EXPR auto Sum( R && r, T init ) {
  return std :: accumulate ( ALL ( r ), init );
}

template < class R >
inline EXPR auto Sum ( R f, R t ) {
  return std ::accumulate ( f, t );
}

template < class R, typename T >
inline EXPR auto Sum ( R f, R t, T init ) {
  return std :: accumulate ( f, t, init );
}

template < class T >
inline EXPR int SZ ( T && x ) { return static_cast < int > ( x.size ( ) ) ; }

template < class T >
INLINE_V constexpr static T inf = std :: numeric_limits < T > :: max ( ) >> 1;

# endif

template < class Os, class T >
inline Os & operator << ( Os & os, T & t ) {
  for ( auto ele : t )
    os << ele << " ";
  os << "\n";
  return os;
}

template < class T >
inline constexpr void clr_cont ( T & cont ) {
  T nw; cont.swap ( nw );
}

# ifndef __GEORGEYUCJR_READ__
# define __GEORGEYUCJR_READ__

# if __cplusplus >= 202000LL && !defined(MACOS) && defined(__unix__)

# define CHECK_EOF 0
# if CHECK_EOF
# define ECHK0 *ptr ? *ptr++ : -1
# define ECHK1                                                                                                                                        \
  if (ch == -1)                                                                                                                                      \
    return set(false), *this;
# define ECHK2                                                                                                                                        \
  if (!*ptr)                                                                                                                                         \
    return set(false), *this;
# define ECHK3 and ch != -1
# define ECHK4 and*ptr
# else
# define ECHK0 *ptr++
# define ECHK1
# define ECHK2
# define ECHK3
# define ECHK4
# endif

# if !defined(MACOS)
# define USE_MMAP
# include <sys/mman.h>
# include <sys/stat.h>
# endif

# if __cpluspls >= 202000LL && !defined(MACOS)
# define DISABLE_RANGE
# endif

# if CHECK_EOF || !defined(USE_MMAP)
# define EV -1
# else
# define EV 0
# endif

namespace FastIO {
template <typename T> struct make_unsigned : public std :: make_unsigned<T> {};
template <> struct make_unsigned<i128> {
  using type = u128;
};
template <typename T>
concept tupleLike = requires(T t) { std :: tuple_size_v<decltype(std :: tuple_cat(t))>; };

inline constexpr ull pw10(int t) { return t == 0 ? 1 : pw10(t - 1) * 10; }

std :: mt19937 mrand(std :: random_device{}());
std :: mt19937_64 mrand64(std :: random_device{}());

inline constexpr static std :: size_t bufSize = 1 << 20;

class IO;
class In {
  friend class IO;

private:
  FILE *inFile;
  bool status = true;
# ifdef USE_MMAP
  struct stat st;
  char *ptr;
  int fd;
# elif !defined(LOCAL)
  char buf[bufSize], *p1, *p2;
# endif

public:
# ifdef LOCAL
  inline int getch() { return fgetc_unlocked(inFile); }
  inline void input(FILE *f) { inFile = f, set(); }
# elif defined(USE_MMAP)
  inline int getch() { return ECHK0; }
  inline void input(FILE *f) {
    inFile = f;
    if (inFile)
      fd = fileno(inFile), fstat(fd, &st), ptr = (char *)mmap(nullptr, st.st_size, PROT_READ, MAP_PRIVATE, fd, 0), set();
  }
  static constexpr auto n = []() {
    std :: array<uint32_t, 0x10000> n{};
    for (int i = 0; i != 0x10000; ++i)
      n[i] = -1;
    constexpr uint32_t e0 = 0x01, e1 = 0x100;
    int x = 0;
    for (uint32_t i = 0, c0 = 0x3030; i != 10; i++, c0 += e0)
      for (uint32_t j = 0, c1 = c0; j != 10; j++, c1 += e1)
        n[c1] = x++;
    return n;
  }();
# else
  inline int getch() { return (p1 == p2 ? (p2 = (p1 = buf) + fread(buf, 1, bufSize, inFile)) : 0), p1 == p2 ? -1 : *p1++; }
  inline void input(FILE *f) { inFile = f, p1 = p2 = buf, set(); }
# endif
  inline void input(const char *s) { input(fopen(s, "rb")); }
  inline void set(bool s = true) { status = s; }
  inline bool get() const { return status; }
};
class Out {
  friend class IO;

public:
  FILE *outFile;
# ifndef LOCAL
  char pbuf[bufSize], *pp;
# endif

public:
# ifdef LOCAL
  inline void flush() { outFile ? fflush(outFile) : 0; }
  inline void putch(char c) { fputc_unlocked(c, outFile); }
# else
  inline void flush() { (outFile ? fwrite(pbuf, 1, pp - pbuf, outFile), fflush(outFile) : 0), pp = pbuf; }
  inline void putch(char c) { ((pp - pbuf == bufSize) ? fwrite(pbuf, 1, bufSize, outFile), pp = pbuf : 0), *pp++ = c; }
# endif
  inline void output(const char *s) { flush(), outFile = fopen(s, "wb"); }
  inline void output(FILE *f) { flush(), outFile = f; }
};
class IO : public In, public Out {
private:
  std :: size_t precision = 12;

public:
  IO(FILE * = nullptr, FILE * = nullptr);
  ~IO() { flush(); }
  static constexpr bool blank(char);
  template <typename... Args>
  requires(sizeof...(Args) > 1)
  IO &read(Args &...);
  template <typename T>
  requires(std :: is_signed_v<T> && std :: is_integral_v<T>) || std :: is_same_v<std :: decay_t<T>, i128>
  IO &read(T &);
  template <typename T>
  requires(std :: is_unsigned_v<T> && std :: is_integral_v<T>) || std :: is_same_v<std :: decay_t<T>, u128>
  IO &read(T &);
  template <typename T>
  requires std :: is_floating_point_v<T>
  IO &read(T &);
  template <typename T> T read();
  IO &read(char &);
  IO &read(char *);
  IO &read(std :: string &);
  IO &readline(char *);
  IO &readline(std :: string &);
  template <tupleLike T> IO &read(T &&);
  template <std :: ranges::input_range R> IO &read(R &&r) { return readArray(std :: forward<R>(r)); }
  void setprecision(std :: size_t n = 6u) { precision = n; }
  template <typename... Args>
  requires(sizeof...(Args) > 1)
  void write(Args &&...);
  inline void write() const {}
  template <typename T>
  requires(std :: is_signed_v<T> && std :: is_integral_v<T>) || std :: is_same_v<std :: decay_t<T>, i128>
  void write(T);
  template <typename T>
  requires(std :: is_unsigned_v<T> && std :: is_integral_v<T>)
  void write(T);
  void write(u128);
  inline void write(char);
  template <typename T>
  requires std :: is_floating_point_v<T>
  void write(T);
  inline void write(bool);
  void write(char *);
  void write(const char *);
  void write(const std :: string &);
  template <typename T> void write(std :: initializer_list<T>);
  template <tupleLike T> void write(T &&);
  template <std :: ranges::input_range R> void write(R &&);
  template <typename... Args> void writeln(Args &&...);
  template <typename T> inline void writespc(T && x);
  operator bool() const { return get(); }
} io(stdin, stdout);
template <typename... Args> inline void writeln(Args &&...x) { io.writeln(std :: forward<Args>(x)...); }
template <typename T> inline void writeln(std :: initializer_list<T> x) { io.writeln(x); }
#pragma endregion

# define isdigit(x) ((x) >= '0' && (x) <= '9')
IO::IO(FILE *in, FILE *out) { input(in), output(out); }
constexpr bool IO::blank(char c) { return c == ' ' || c == '\n' || c == '\r'; }
template <typename... Args>
requires(sizeof...(Args) > 1)
IO &IO::read(Args &...args) {
  if constexpr (CHECK_EOF)
    (read(args) && ...);
  else
    (read(args), ...);
  return *this;
}
template <typename T>
requires(std :: is_signed_v<T> && std :: is_integral_v<T>) || std :: is_same_v<std :: decay_t<T>, i128>
IO &IO::read(T &x) {
  x = 0;
  static typename make_unsigned<T>::type t;
  bool sign = false;
# ifndef USE_MMAP
  int ch = getch();
  while (!isdigit(ch) ECHK3)
    sign = (ch == '-'), ch = getch();
  ECHK1
  t = 0;
  while (isdigit(ch))
    t = t * 10 + (ch ^ 48), ch = getch();
# else
  while (!isdigit(*ptr) ECHK4)
    sign = *ptr++ == '-';
  ECHK2
  t = *ptr++ ^ 48;
  while (~n[*reinterpret_cast<std :: uint16_t *&>(ptr)])
    t = t * 100 + n[*reinterpret_cast<std :: uint16_t *&>(ptr)++];
  if (isdigit(*ptr))
    t = t * 10 + (*ptr++ ^ 48);
# endif
  x = sign ? (~t + 1) : t;
  return *this;
}
template <typename T>
requires(std :: is_unsigned_v<T> && std :: is_integral_v<T>) || std :: is_same_v<std :: decay_t<T>, u128>
IO &IO::read(T &x) {
  x = 0;
# ifndef USE_MMAP
  int ch = getch();
  while (!isdigit(ch) ECHK3)
    ch = getch();
  ECHK1
  while (isdigit(ch))
    x = (x << 1) + (x << 3) + (ch ^ 48), ch = getch();
# else
  while (!isdigit(*ptr) ECHK4)
    ptr++;
  ECHK2
  x = *ptr++ ^ 48;
  while (~n[*reinterpret_cast<std :: uint16_t *&>(ptr)])
    x = x * 100 + n[*reinterpret_cast<std :: uint16_t *&>(ptr)++];
  if (isdigit(*ptr))
    x = x * 10 + (*ptr++ ^ 48);
# endif
  return *this;
}
template <typename T>
requires std :: is_floating_point_v<T>
IO &IO::read(T &x) {
  x = 0;
  T t = 1;
  bool sign = false;
  int ch = getch();
  while (!isdigit(ch) ECHK3)
    sign = (ch == '-'), ch = getch();
  ECHK1
  while (isdigit(ch))
    x = x * 10 + (ch ^ 48), ch = getch();
  if (ch == '.')
    for (ch = getch(); isdigit(ch); ch = getch())
      x += (t /= 10) * (ch ^ 48);
  x = sign ? -x : x;
  return *this;
}
template <typename T> T IO::read() {
  static std :: decay_t<T> x;
  return read(x), x;
}
IO &IO::read(char &ch) {
  do
    ch = getch();
  while (blank(ch));
  ECHK1
  return *this;
}
IO &IO::read(char *s) {
  int ch = getch();
  while (blank(ch))
    ch = getch();
  ECHK1
  while (!blank(ch) && ch != EV)
    *s++ = ch, ch = getch();
  *s = 0;
  return *this;
}
IO &IO::read(std :: string &s) {
  int ch = getch();
  while (blank(ch))
    ch = getch();
  ECHK1
  s.erase();
  while (!blank(ch) && ch != EV)
    s.append(1, ch), ch = getch();
  return *this;
}
IO &IO::readline(char *s) {
  char *t = s;
  int ch = getch();
  while (ch != '\n' && ch != EV)
    *s++ = ch, ch = getch();
  *s = 0;
  if (s == t && ch != '\n')
    set(false);
  return *this;
}
IO &IO::readline(std :: string &s) {
  s.erase();
  int ch = getch();
  while (ch != '\n' && ch != EV)
    s.append(1, ch), ch = getch();
  if (s.empty() && ch != '\n')
    set(false);
  return *this;
}
template <tupleLike T> IO &IO::read(T &&t) {
  std :: apply([&](auto & ...t) { (read(t), ...); }, t);
  return *this;
}
template <typename... Args>
requires(sizeof...(Args) > 1)
void IO::write(Args &&...args) {
  (write(std :: forward<Args>(args)), ...);
}
template <typename T>
requires(std :: is_signed_v<T> && std :: is_integral_v<T>) || std :: is_same_v<std :: decay_t<T>, i128>
void IO::write(T x) {
  static typename make_unsigned<T>::type y;
  y = x;
  if (x < 0)
    putch('-'), write(~y + 1);
  else
    write(y);
}
constexpr auto D = []() {
  constexpr uint32_t e0 = 0x1, e1 = 0x100, e2 = 0x10000, e3 = 0x1000000;
  std :: array<uint32_t, 10000> m{};
  int x = 0;
  for (uint32_t i = 0, c0 = 0x30303030; i != 10; i++, c0 += e0)
    for (uint32_t j = 0, c1 = c0; j != 10; j++, c1 += e1)
      for (uint32_t k = 0, c2 = c1; k != 10; k++, c2 += e2)
        for (uint32_t l = 0, c3 = c2; l != 10; l++, c3 += e3)
          m[x++] = c3;
  return m;
}();
template <typename T>
requires(std :: is_unsigned_v<T> && std :: is_integral_v<T>)
void IO::write(T x) {
# ifndef LOCAL
  if (std :: end(pbuf) - pp < 64)
    flush();

  auto L = [&](int x) { return x == 1 ? 0 : pw10(x - 1); };
  auto R = [&](int x) { return pw10(x) - 1; };

# define de(t)                                                                                                                                        \
  case L(t)... R(t):                                                                                                                                 \
    *reinterpret_cast<uint32_t *>(pp) = D[x / pw10((t)-4)];                                                                                          \
    pp += 4;                                                                                                                                         \
    x %= pw10((t)-4);

  ull y = x;
  switch (y) {
    de(18);
    de(14);
    de(10);
    de(6);
  case L(2)... R(2):
    *reinterpret_cast<uint32_t *>(pp) = D[x * 100];
    pp += 2;
    break;

    de(17);
    de(13);
    de(9);
    de(5);
  case L(1)... R(1):
    *pp = static_cast<char>('0' + x);
    pp += 1;
    break;

  default:
    *reinterpret_cast<uint32_t *>(pp) = D[x / pw10(16)];
    pp += 4;
    x %= pw10(16);
    de(16);
    de(12);
    de(8);
  case L(4)... R(4):
    *reinterpret_cast<uint32_t *>(pp) = D[x];
    pp += 4;
    break;

    de(19);
    de(15);
    de(11);
    de(7);
  case L(3)... R(3):
    *reinterpret_cast<uint32_t *>(pp) = D[x * 10];
    pp += 3;
    break;
  }
# else
  write(u128(x));
# endif
}
constexpr u128 _pw10(int x) { return x == 0 ? 1 : _pw10(x - 1) * 10; }
void IO::write(u128 x) {
  if (std :: end(pbuf) - pp < 64)
    flush();
  constexpr auto pw10 = _pw10;
  auto L = [&](int x) { return x == 1 ? 0 : pw10(x - 1); };
  auto R = [&](int x) { return pw10(x) - 1; };

# define de(t)                                                                                                                                        \
  case L(t)... R(t):                                                                                                                                 \
    *reinterpret_cast<uint32_t *>(pp) = D[x / pw10((t)-4)];                                                                                          \
    pp += 4;                                                                                                                                         \
    x %= pw10((t)-4);

  switch (x) {
    de(38);
    de(34);
    de(30);
    de(26);
    de(22);
    de(18);
    de(14);
    de(10);
    de(6);
  case L(2)... R(2):
    *reinterpret_cast<uint32_t *>(pp) = D[x * 100];
    pp += 2;
    break;

    de(37);
    de(33);
    de(29);
    de(25);
    de(21);
    de(17);
    de(13);
    de(9);
    de(5);
  case L(1)... R(1):
    *pp = static_cast<char>('0' + x);
    pp += 1;
    break;

    de(36);
    de(32);
    de(28);
    de(24);
    de(20);
    de(16);
    de(12);
    de(8);
  case L(4)... R(4):
    *reinterpret_cast<uint32_t *>(pp) = D[x];
    pp += 4;
    break;

  default:
    *reinterpret_cast<uint32_t *>(pp) = D[x / pw10(35)];
    pp += 4;
    x %= pw10(35);
    de(35);
    de(31);
    de(27);
    de(23);
    de(19);
    de(15);
    de(11);
    de(7);
  case L(3)... R(3):
    *reinterpret_cast<uint32_t *>(pp) = D[x * 10];
    pp += 3;
    break;
  }
}
void IO::write(bool x) { putch(x ^ 48); }
void IO::write(char c) { putch(c); }
template <typename T>
requires std :: is_floating_point_v<T>
void IO::write(T x) {
  static char buf[512];
  *std :: to_chars(buf, buf + 512, x, std :: chars_format::fixed, precision).ptr = 0;
  write(buf);
}
void IO::write(char *s) {
  while (*s)
    putch(*s++);
}
void IO::write(const char *s) {
  while (*s)
    putch(*s++);
}
void IO::write(const std :: string &s) { write(s.data()); }
template <typename T> void IO::write(std :: initializer_list<T> t) {
  auto first = std :: begin(t), last = std :: end(t);
  if (first != last)
    for (write(*first++); first != last; ++first) {
      putch(' ');
      write(*first);
    }
}
template <tupleLike T> void IO::write(T &&t) {
  [&]<std :: size_t... I>(std :: index_sequence<I...>) {
    (..., (I == 0 ? void(0) : putch(' '), write(std :: get<I>(t))));
  }(std :: make_index_sequence<std :: tuple_size_v<std :: remove_reference_t<T>>>());
}
template <std :: ranges::input_range R> void IO::write(R &&r) {
  if constexpr (std :: is_same_v<std :: decay_t<R>, std :: string>)
    return write(r.data());
  auto first = std :: ranges::begin(r), last = std :: ranges::end(r);
  if (first != last)
    for (write(*first++); first != last; ++first) {
      putch(' ');
      write(*first);
    }
}
template <typename... Args> void IO::writeln(Args &&...x) { write(std :: forward<Args>(x)...), putch('\n'); }
template <typename T> inline void IO::writespc(T && x) { write(x), putch('\n'); }
} // namespace FastIO
using namespace FastIO;

# else

# ifndef LUOGU
# define auto_att __attribute__((target("avx2"), optimize(3, "Ofast", "unroll-loops", "inline")))
# else
# define auto_att
# endif

namespace FastIO {
# define endl '\n'
INLINE_V static constexpr size_t buf_size = 1 << 18;
INLINE_V static constexpr size_t integer_size = 20;
INLINE_V static constexpr size_t block_size = 10000;

static char inbuf[buf_size + 1] = {};
static char outbuf[buf_size + 1] = {};
static char block_str[block_size * 4 + 1] = {};

static constexpr uint64_t power10[] = {1,
                                       10,
                                       100,
                                       1000,
                                       10000,
                                       100000,
                                       1000000,
                                       10000000,
                                       100000000,
                                       1000000000,
                                       10000000000,
                                       100000000000,
                                       1000000000000,
                                       10000000000000,
                                       100000000000000,
                                       1000000000000000,
                                       10000000000000000,
                                       100000000000000000,
                                       1000000000000000000,
                                       10000000000000000000u
                                      };

struct Scanner {
# ifndef LOCAL
private:
  size_t pos, end;

  inline void load() {
    end = fread(inbuf, 1, buf_size, stdin);
    inbuf[end] = '\0';
  }
  inline void reload() {
    size_t len = end - pos;
    memmove(inbuf, inbuf + pos, len);
    end = len + fread(inbuf + len, 1, buf_size - len, stdin);
    inbuf[end] = '\0';
    pos = 0;
  }
  inline void skip_space() {
    while (inbuf[pos] <= ' ') {
      if (__builtin_expect(++pos == end, 0))
        reload();
    }
  }
  inline char get_next() { return inbuf[pos++]; }
  inline char get_next_nonspace() {
    skip_space();
    return inbuf[pos++];
  }

public:
  Scanner() { load(); }

  auto_att inline void read(char &c) { c = get_next_nonspace(); }
  auto_att inline void read(std :: string &s) {
    skip_space();
    s = "";
    do {
      size_t start = pos;
      while (inbuf[pos] > ' ')
        ++pos;
      s += std :: string(inbuf + start, inbuf + pos);
      if (inbuf[pos] != '\0')
        break;
      reload();
    } while (true);
  }

  template <class T> typename std :: enable_if<std :: is_integral<T>::value, void>::type read(T &x) {
    char c = get_next_nonspace();
    if (__builtin_expect(pos + integer_size >= end, 0))
      reload();
    bool neg = false;
    if (c == '-')
      neg = true, x = 0;
    else
      x = c & 15;
    while ((c = get_next()) >= '0')
      x = (x << 3) + (x << 1) + (c & 15);
    if (neg)
      x = -x;
  }
# else
  template <typename _Tp> inline void read(_Tp &x) {
    char ch = getchar();
    int f = 1;
    x = 0;
    for (; ch < '0' || ch > '9'; ch = getchar())
      f = ch == '-' ? -1 : 1;
    for (; ch >= '0' && ch <= '9'; ch = getchar())
      x = (x << 3) + (x << 1) + (ch ^ 48);
    x *= f;
  }
  inline void read(char &c) { c = getchar(); }
  inline void read(char *x) {
    int i = 0;
    char c = ' ';
    for (; c <= ' ';)
      c = getchar();
    for (; c > ' ';)
      x[i++] = c, c = getchar();
    x[i] = 0;
  }
  inline void read(std :: string &x) {
    x.clear();
    char c = ' ';
    for (; c <= ' ';)
      c = getchar();
    for (; c > ' ';)
      x += c, c = getchar();
  }
# endif
  template <class Head, class... Others> void read(Head &head, Others &...others) {
    read(head);
    read(others...);
  }
  template <class T1, class T2> inline void read(std :: pair<T1, T2> &x) { read(x.first), read(x.second); }
} is;

struct Printer {
# ifndef LOCAL
private:
  size_t pos = 0;

  auto_att inline void flush() {
    fwrite(outbuf, 1, pos, stdout);
    pos = 0;
  }

  inline void pre_calc() {
    for (size_t i = 0; i < block_size; ++i) {
      size_t j = 4, k = i;
      while (j--) {
        block_str[i * 4 + j] = k % 10 | 48;
        k /= 10;
      }
    }
  }

  static EXPR size_t get_integer_size(uint64_t n) {
    if (n >= power10[10]) {
      if (n >= power10[19])
        return 20;
      if (n >= power10[18])
        return 19;
      if (n >= power10[17])
        return 18;
      if (n >= power10[16])
        return 17;
      if (n >= power10[15])
        return 16;
      if (n >= power10[14])
        return 15;
      if (n >= power10[13])
        return 14;
      if (n >= power10[12])
        return 13;
      if (n >= power10[11])
        return 12;
      return 11;
    } else {
      if (n >= power10[9])
        return 10;
      if (n >= power10[8])
        return 9;
      if (n >= power10[7])
        return 8;
      if (n >= power10[6])
        return 7;
      if (n >= power10[5])
        return 6;
      if (n >= power10[4])
        return 5;
      if (n >= power10[3])
        return 4;
      if (n >= power10[2])
        return 3;
      if (n >= power10[1])
        return 2;
      return 1;
    }
  }

public:
  Printer() { pre_calc(); }
  ~Printer() { flush(); }
  inline void write(char c) {
    outbuf[pos++] = c;
    if (__builtin_expect(pos == buf_size, 0))
      flush();
  }
  inline void write(const char *s) {
    while (*s != 0) {
      outbuf[pos++] = *s++;
      if (__builtin_expect(pos == buf_size, 0))
        flush();
    }
  }
  inline void write(const std :: string &s) {
    for (auto c : s) {
      outbuf[pos++] = c;
      if (__builtin_expect(pos == buf_size, 0))
        flush();
    }
  }

  template <class T> typename std :: enable_if<std :: is_integral<T>::value, void>::type write(T x) {
    if (__builtin_expect(pos + integer_size >= buf_size, 0))
      flush();
    if (x < 0)
      write('-'), x = -x;
    size_t digit = get_integer_size(x);
    size_t len = digit;
    while (len >= 4) {
      len -= 4;
      memcpy(outbuf + pos + len, block_str + ((x % block_size) << 2), 4);
      x /= block_size;
    }
    memcpy(outbuf + pos, block_str + (x << 2) + (4 - len), len);
    pos += digit;
  }
# else
  inline void write(char c) { putchar(c); }
  inline void write(const char *x) {
    for (int i = 0; x[i]; ++i)
      write(x[i]);
  }
  inline void write(std::string s) {
    for (auto c : s)
      write(c);
  }
  template <typename _Tp> inline void write(_Tp x) {
    if (x < 0)
      putchar('-'), x = -x;
    if (x > 9)
      write(x / 10);
    putchar(x % 10 ^ 48);
  }
# endif
  template <class Head, class... Others> void write(const Head &head, const Others &...others) {
    write(head);
    write(' ');
    write(others...);
  }

  template <class... Args> void writeln(const Args &...args) {
    write(args...);
    write('\n');
  }
  template < class T >
  inline void writespc ( const T & x ) {
    write ( x );
    write ( " " );
  }
  template <class T1, class T2> inline void write(const std :: pair<T1, T2> &x) { write(x.first, x.second); }
} os;

struct IO : public Scanner, public Printer {
} io;
}; // namespace FastIO
using namespace FastIO;
# endif
# endif
using namespace std;

# warning Do not use debug.hpp.

# ifndef GY_MMint
# define GY_MMint

namespace georgeyucjr{
namespace internal
{
template <typename T>
struct mkdbwd
{
};
template <>
struct mkdbwd<std ::uint8_t>
{
  using type = std ::uint16_t;
};
template <>
struct mkdbwd<std ::uint16_t>
{
  using type = std ::uint32_t;
};
template <>
struct mkdbwd<std ::uint32_t>
{
  using type = std ::uint64_t;
};
template <>
struct mkdbwd<std ::uint64_t>
{
  using type = unsigned __int128;
};
template <typename T>
using mkdbwd_t = mkdbwd<T>::type;
inline constexpr auto flr(auto &&x, auto &&y)
{
  return x / y - (x % y && (x ^ y) < 0);
}
inline constexpr auto divmod(auto x, auto y)
{
  auto &&q = flr(x, y);
  return std::make_pair(q, x - q * y);
}
} // namespace internal

using namespace internal;
template <typename T>
struct MontgomeryReduction
{
  using int_type = T;
  using int_double_t = mkdbwd_t<T>;
  inline constexpr static int bsw = std::numeric_limits<T>::digits;
  inline constexpr explicit MontgomeryReduction(T mod)
    : _mod(mod),
      _mod_neg_inv(inv_base(~(mod - 1))),
      mbs((int_double_t(1) << bsw) % mod),
      mbs2(int_double_t(mbs) * mbs % mod),
      mbs3(int_double_t(mbs2) * mbs % mod) {}
  inline constexpr T mod() const { return _mod; }
  inline constexpr T mbase() const { return mbs; }
  inline constexpr T mbase2() const { return mbs2; }
  inline constexpr T mbase3() const { return mbs3; }
  inline constexpr T reduce(int_double_t t) const
  {
    return (t + int_double_t(T(t) * _mod_neg_inv) * _mod) >> bsw;
  }
  inline constexpr T unsafemod(T x) const { return x >= _mod * 2 ? x - _mod * 2 : x; }
  inline constexpr T safemod(T x) const { return x >= _mod ? x - _mod : x; }
  inline constexpr static T inv_base(T x)
  {
    T y = 1;
    for (int i = 1; i < bsw; i <<= 1)
      y *= 2 - x * y;
    return y;
  }

private:
  T _mod, _mod_neg_inv, mbs, mbs2, mbs3;
};
template <std::unsigned_integral T, typename S = std::make_signed_t<T>>
inline constexpr std::tuple<S, S, T> clc(T x, T y)
{
  bool t = x < y;
  if (t)
    swap(x, y);
  if (y == 0)
  {
    if (x == 0)
      return {};
    if (t)
      return {0, 1, x};
    return {1, 0, x};
  }
  S s0 = 1, s1 = 0, t0 = 0, t1 = 1;
  while (true)
  {
    auto [q, r] = divmod(x, y);
    if (r == 0)
    {
      if (t)
        return {t1, s1, y} ;
      return {s1, t1, y};
    }
    S s2 = s0 - S(q) * s1, t2 = t0 - S(q) * t1;
    x = y,
    y = r,
    s0 = s1,
    s1 = s2,
    t0 = t1,
    t1 = t2;
  }
}
template <std::unsigned_integral T>
inline constexpr T modinv(T x, T m)
{
  auto [s, t, g] = clc(x, m);
  assert(g == 1);
  return s < 0 ? T(s) + m : s;
}
template <typename T>
inline constexpr T Qpow(T a, auto b)
{
  T ans{1};
  for (; b; b >>= 1, a *= a)
    if (b & 1)
      ans *= a;
  return ans;
}
template <typename Context>
struct MontgomeryModInt
{
  using mint = MontgomeryModInt;
  using int_type = Context::int_type;
  using mr_type = Context::mr_type;
  using int_double_t = mr_type::int_double_t;
  inline constexpr MontgomeryModInt() = default;
  inline constexpr MontgomeryModInt(long long y)
  {
    using S = std::make_signed_t<int_type>;
    S v = y % S(mod());
    x = mr().reduce(mr().mbase2() * int_double_t(v < 0 ? v + mod() : v));
  }
  inline constexpr MontgomeryModInt(int y)
  {
    using S = std::make_signed_t<int_type>;
    S v = y % S(mod());
    x = mr().reduce(mr().mbase2() * int_double_t(v < 0 ? v + mod() : v));
  }
  inline constexpr MontgomeryModInt(unsigned int y)
  {
    x = mr().reduce(mr().mbase2() * int_double_t(y % mod()));
  }
  inline constexpr MontgomeryModInt(unsigned long long y)
  {
    x = mr().reduce(mr().mbase2() * int_double_t(y % mod()));
  }
  inline constexpr int_type val() const { return mr().safemod(mr().reduce(x)); }
  inline constexpr int_type residue() const { return mr().safemod(x); }
  inline constexpr static int_type mod() { return mr().mod(); }
  inline constexpr mint &operator++()
  {
    x = mr().unsafemod(x + mr().mbase());
    return *this;
  }
  inline constexpr mint operator++(int)
  {
    mint r = *this;
    ++*this;
    return r;
  }
  inline constexpr mint &operator+=(const mint &rhs)
  {
    x = mr().unsafemod(x + rhs.x);
    return *this;
  }
  inline constexpr mint &operator--()
  {
    x = mr().unsafemod(x + mod() - mr().mbase());
    return *this;
  }
  inline constexpr mint operator--(int)
  {
    mint r = *this;
    --*this;
    return r;
  }
  inline constexpr mint &operator-=(const mint &rhs)
  {
    x = mr().unsafemod(x + mod() * 2 - rhs.x);
    return *this;
  }
  inline constexpr mint &operator*=(const mint &rhs)
  {
    x = mr().reduce(int_double_t(x) * rhs.x);
    return *this;
  }
  inline constexpr mint inv() const
  {
    return from_raw(
             mr().reduce(int_double_t(mr().mbase3()) * modinv(x, mod())));
  }
  inline constexpr mint pow(auto n) const { return Qpow(*this, n); }
  inline constexpr mint &operator/=(const mint &rhs) { return *this *= rhs.inv(); }
  inline constexpr mint operator+() const { return *this; }
  inline constexpr mint operator-() const { return from_raw(!x ? 0 : mod() * 2 - x); }
  inline friend constexpr mint operator+(mint lhs, const mint &rhs)
  {
    return lhs += rhs;
  }
  inline friend constexpr mint operator-(mint lhs, const mint &rhs)
  {
    return lhs -= rhs;
  }
  inline friend constexpr mint operator*(mint lhs, const mint &rhs)
  {
    return lhs *= rhs;
  }
  inline friend constexpr mint operator/(mint lhs, const mint &rhs)
  {
    return lhs /= rhs;
  }
  inline friend constexpr bool operator==(const mint &lhs, const mint &rhs)
  {
    return mr().safemod(lhs.x) == mr().safemod(rhs.x);
  }
  inline friend constexpr auto operator<=> (const mint &lhs, const mint &rhs)
  {
    return mr().safemod(lhs.x) <=> mr().safemod(rhs.x);
  }
  inline constexpr static mint from_raw(int_type x)
  {
    mint r;
    r.x = x;
    return r;
  }
  inline constexpr int_type raw() const { return x; }
#ifdef __GEORGEYUCJR_READ__
  inline void write(IO &io) const { io.write(val()); }
#else
  inline friend std::ostream &operator<<(std::ostream &os, const mint &x)
  {
    return os << x.val();
  }
#endif
  inline constexpr static const mr_type &mr()
  {
    return Context::montgomery_reduction();
  }

private:
  int_type x{};
};
template <std::unsigned_integral T, T Mod>
requires(Mod % 2 == 1 && Mod <= std::numeric_limits<T>::max() / 2)
struct StaticMontgomeryReductionContext
{
  using int_type = T;
  using mr_type = MontgomeryReduction<T>;
  constexpr static const mr_type &montgomery_reduction() { return _reduction; }

private:
  constexpr static auto _reduction = mr_type(Mod);
};
template <std::unsigned_integral T>
struct DynamicMontgomeryReductionContext
{
  using int_type = T;
  using mr_type = MontgomeryReduction<T>;
  struct Guard
  {
    Guard(const Guard &) = delete;
    Guard(Guard &&) = delete;
    Guard &operator=(const Guard &) = delete;
    Guard &operator=(Guard &&) = delete;
    ~Guard() { _reduction_env.pop_back(); }

  private:
    friend DynamicMontgomeryReductionContext;
    Guard() = default;
  };
  [[nodiscard]] inline static Guard set_mod(T mod)
  {
    assert(mod % 2 == 1 && mod <= std::numeric_limits<T>::max() / 4);
    _reduction_env.emplace_back(mod);
    return {};
  }
  inline constexpr static const mr_type &montgomery_reduction()
  {
    return _reduction_env.back();
  }

private:
  inline static std ::vector<mr_type> _reduction_env;
};

template <std ::uint32_t Mod>
using static_modint = MontgomeryModInt<StaticMontgomeryReductionContext<std ::uint32_t, Mod>>;

template <std ::uint64_t Mod>
using static_modint_64 = MontgomeryModInt<StaticMontgomeryReductionContext<std ::uint64_t, Mod>>;

using modint998244353 = static_modint<998244353>;

using modint1000000007 = static_modint<1000000007>;

#define dymanic_modint_IN(_Tp, Mod)                                      \
    using dymanic_modint_type = DynamicMontgomeryReductionContext<_Tp>; \
    auto _guard = dymanic_modint_type ::set_mod();                      \
    using mint = MontgomeryModInt<dymanic_modint_type>;

#define dymanic_modint(_Tp, Mod)                                      \
    using dymanic_modint_type = georgeyucjr::DynamicMontgomeryReductionContext<_Tp>; \
    auto _guard = dymanic_modint_type ::set_mod(Mod);                      \
    using mint = georgeyucjr::MontgomeryModInt<dymanic_modint_type>;
} // namespace georgeyucjr

# endif

template < class Mint > class Comb {
private: std :: vector < Mint > fac; std :: vector < Mint > ifac;
public: inline void rsz ( int _n ) {
    int prv_n = ( int ) fac.size ( ) - 1; if (prv_n >= _n) return ; fac.resize(_n + 1), ifac.resize(_n + 1);
    for (int i = prv_n + 1; i <= _n; ++i) fac[i] = fac[i - 1] * Mint(i); ifac[_n] = fac[_n].inv();
    for (int i = _n; i > prv_n; --i) ifac[i - 1] = ifac[i] * Mint(i);
  } Comb ( int n = 1 ) { fac.assign(2, Mint(1)), ifac.assign(2, Mint(1)), rsz(n); } inline Mint Fac(int n) {
    if ( n >= fac.size ( ) ) rsz ( n + 5 ); return fac[n];
  } inline Mint InvFac(int n) {
    if (n >= fac.size()) rsz(n + 5); return ifac[n];
  } inline Mint Inv(int n) {
    if (n >= fac.size()) rsz(n + 5); return ifac[n] * fac[n - 1];
  } inline Mint C(int n, int m) {
    if (n < 0 || n < m || m < 0) return Mint(0); if (n >= fac.size()) rsz(n + 5); return fac[n] * ifac[m] * ifac[n - m];
  } inline Mint A(int n, int m) {
    if (n < 0 || n < m || m < 0) return Mint(0); if (n >= fac.size()) rsz(n + 5); return fac[n] * ifac[n - m];
  } inline Mint operator()(int n, int m) { return C(n, m); }
};

using mint = georgeyucjr :: modint998244353;

Comb < mint > cmb;

signed main() {
  int T; io.read(T);
  auto slv = [ & ] ( ) {
    int a, b, c, d;
    io.read(a, b, c, d);
    int t = d + d + c - b - a - a;
    if (!t)
      return io.writeln(0), void();
    if (t < 0) swap(a, d), swap(b, c);
    auto clc = [&](int a, int b, int c, int d) {
      d -= b + b;
      if (b < 0 || c < 0 || d < 0)return mint(0);
      return cmb.Fac(b + c + d) * cmb.InvFac(b) * cmb.InvFac(c) * cmb.InvFac(d) * a;
    };
    if (!a)
      io.writeln((clc(1, b, c, d) + clc(2, b - 1, c, d - 1) + clc(1, b - 2, c, d - 2)).val());
    else
      io.writeln((clc(a + 1, b - 2, c, d - a - 2) + clc(a + a, b - 1, c - 1, d - a - 1) + clc(a - 1, b, c - 2, d - a) + clc(2, b - 1, c, d - a - 1) + clc(2, b, c - 1, d - a)).val());
  }; while ( T-- ) slv ( );
# if defined(LOCAL) && !defined(CPH)
  cerr << "Spend time : " << clock ( ) * 1. / CLOCKS_PER_SEC * 1000. << "ms\n";
# endif
  return 0;
}