#pragma GCC optimize("-Ofast","-funroll-all-loops","-ffast-math")
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef pair<int,int> pii;
typedef long long ll;
typedef double ld;
typedef vector<int> vi;
#define fi first
#define se second
#define fe first
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);}
#define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}
#define es(x,e) (int e=fst[x];e;e=nxt[e])
#define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e])
const int MOD=998244353;
#define SZ 12345678
int fac[SZ],rfac[SZ];
ll qp(ll a,ll b)
{
    ll x=1; a%=MOD;
    while(b)
    {
        if(b&1) x=x*a%MOD;
        a=a*a%MOD; b>>=1;
    }
    return x;
}

using i64=ll;

int mod_inv(int a, int mod) {
  int b = mod, s = 1, t = 0, old_a = a;
  while (b) {
    int q = a / b;
    swap(a %= b, b);
    swap(s -= t * q, t);
  }
  if (a != 1) {
    fprintf(stderr,
      "Error: %d^{-1} mod %d does not exist.\n\n", old_a, mod);
    assert(0);
  }
  return s < 0 ? s + mod : s;
}

vector<int> extended(int n, 
    const vector< vector<int> >& coeffs, const vector<int>& terms, int mod) {

  vector<int> ret(max<int>(n + 1, terms.size()));
  copy(terms.begin(), terms.end(), ret.begin());
  const int order = coeffs.size() - 1;
  const int deg = coeffs[0].size() - 1;
  assert((int) terms.size() >= order);
  for (int m = terms.size(); m <= n; ++m) {
    int s = 0;
    for (int i = 1; i <= order; ++i) {
      int k = m - i, t = ret[k];
      for (int d = 0; d <= deg; ++d) {
        s = (s + i64(t) * coeffs[i][d]) % mod;
        t = i64(t) * k % mod;
      }
    }
    int denom = 0, mpow = 1;
    for (int d = 0; d <= deg; ++d) {
      denom = (denom + i64(mpow) * coeffs[0][d]) % mod;
      mpow = i64(mpow) * m % mod;
    }
    ret[m] = i64(mod - s) * mod_inv(denom, mod) % mod;
  }
  return ret;
}

vector< vector<int> > find_recurrence_relation(
    const vector<int>& terms, const int deg, const int mod, bool verify=true) {

  const int n = terms.size();
  const int B = (n + 2) / (deg + 2); // number of blocks
  const int C = B * (deg + 1); // number of columns
  const int R = n - (B - 1); // number of rows
  assert(B >= 2); assert(R >= C - 1);

  auto mul = [mod] (int a, int b) { return i64(a) * b % mod; };
  auto fixed = [mod] (int a) { return (a %= mod) < 0 ? a + mod : a; };
  auto error = [] (int order, int deg) {
      throw "GG";
  };

  vector< vector<int> > mat(R, vector<int>(C));
  for (int y = 0; y < R; ++y) {
    for (int b = 0; b < B; ++b) {
      for (int d = 0, v = fixed(terms[y + b]); d <= deg; ++d) {
        mat[y][b * (deg + 1) + d] = v;
        v = mul(v, y + b);
      }
    }
  }

  int rank = 0;
  for (int x = 0; x < C; ++x) {
    int pivot = -1;
    for (int y = rank; y < R; ++y) if (mat[y][x] != 0) {
      pivot = y; break;
    }
    if (pivot < 0) break;
    if (pivot != rank) swap(mat[rank], mat[pivot]);
    int inv = mod_inv(mat[rank][x], mod);
    for (int x2 = x; x2 < C; ++x2) mat[rank][x2] = mul(mat[rank][x2], inv);
    for (int y = rank + 1; y < R; ++y) if (mat[y][x]) {
      int c = mod - mat[y][x];
      for (int x2 = x; x2 < C; ++x2) {
        mat[y][x2] = (i64(mat[y][x2]) + i64(c) * mat[rank][x2]) % mod;
      }
    }
    ++rank;
  }

  if (rank == C) error(B - 1, deg);

  for (int y = rank - 1; y >= 0; --y) if (mat[y][rank]) {
    assert(mat[y][y] == 1);
    int c = mod - mat[y][rank];
    for (int y2 = 0; y2 < y; ++y2) {
      mat[y2][rank] = (mat[y2][rank] + i64(c) * mat[y2][y]) % mod;
    }
  }

  int order = rank / (deg + 1);
  vector< vector<int> > ret(order + 1, vector<int>(deg + 1));
  ret[0][rank % (deg + 1)] = 1;
  for (int y = rank - 1; y >= 0; --y) {
    int k = order - y / (deg + 1), d = y % (deg + 1);
    ret[k][d] = (mod - mat[y][rank]) % mod;
  }

  if (verify) {
    auto extended_terms = extended(n - 1, ret, 
        vector<int>(terms.begin(), terms.begin() + order), mod);
    for (int i = 0; i < (int) terms.size(); ++i) {
      if (fixed(terms[i] - extended_terms[i]) != 0) error(B - 1, deg);
    }
  }

  auto verbose = [&] {
    int last = verify ? n - 1 : order + R - 1;
    if((last + 1) - ((deg + 2) * (order + 1) - 2)<=100)
        throw "GG";
  };
  verbose();

  return ret;
}

vector<int> show_extended_sequence(int n, const vector<int>& terms, int degree, int mod) {
  auto coeffs = find_recurrence_relation(terms, degree, mod);
  auto extended_terms = extended(n, coeffs, terms, mod);
  extended_terms.resize(n); return extended_terms;
}

#define SS 12345678
int T,n,c,op[SS];
int main()
{
    cin>>T;
    fac[0]=1; for(int i=1;i<SZ;++i) fac[i]=fac[i-1]*(ll)i%MOD;
    rfac[SZ-1]=qp(fac[SZ-1],MOD-2);
    for(int i=SZ-1;i;--i) rfac[i-1]=rfac[i]*(ll)i%MOD;
    while(T--)
    {
    cin>>n>>c;
    c=(c*2+1)%MOD;
    vector<int> ww;
    for(int i=0;i<=200;++i) {
        ll po=1,ans=0;
        for(int j=0;j<=i;++j) {
            ll C=fac[i]*(ll)rfac[j]%MOD*rfac[i-j]%MOD;
            ans+=C*C%MOD*po;ans%=MOD;po=po*c%MOD;
        }
        ans=(ans%MOD+MOD)%MOD;
        ww.pb(ans); op[i]=ans;
//        ans=ans*rfac[i]%MOD*rfac[i]%MOD;
    }
    auto coeffs=find_recurrence_relation(ww,1,MOD);
//    cout<<coeffs[0][0]<<","<<coeffs[0][1]<<"??\n";
    const int mod=MOD;
      const int order = coeffs.size() - 1;
      const int deg = coeffs[0].size() - 1;
      for (int m = 201; m <= n; ++m) {
        int s = 0;
        for (int i = 1; i <= order; ++i) {
          int k = m - i, t = op[k];
          for (int d = 0; d <= deg; ++d) {
            s = (s + i64(t) * coeffs[i][d]) % mod;
            t = i64(t) * k % mod;
          }
        }
//        cout<<m<<":"<<denom<<"\n";
        op[m] = i64(mod - s) * rfac[m]%mod*fac[m-1]%mod;
      }
      int ans=0;
      for (int m = 1; m <= n; ++m)
          ans^=(op[m]%MOD+MOD)%MOD;
    printf("%d\n",ans);
    }
}