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

const int N = 1e7 + 5, P = 998244353;
int fac[N], ifac[N], inv[N], q[N];

int power(int a, int x) {
  int ans = 1;
  for (; x; x >>= 1, a = 1ll * a * a % P)
    if (x & 1) ans = 1ll * ans * a % P;
  return ans;
}
int binom(int n, int m) {
  return 1ll * fac[n] * ifac[m] % P * ifac[n - m] % P;
}

int main() {
  inv[1] = 1;
  for (int i = 2; i < N; ++i) inv[i] = 1ll * (P - P / i) * inv[P % i] % P;
  for (int i = fac[0] = ifac[0] = 1; i < N; ++i) {
    fac[i] = 1ll * fac[i - 1] * i % P;
    ifac[i] = 1ll * ifac[i - 1] * inv[i] % P;
  }
  int T;
  scanf("%d", &T);
  while (T--) {
    int n, c;
    scanf("%d%d", &n, &c);
    if (c == 998244352) {
      int now = P - 1, xorsum = 0;
      for (int k = 2; k <= n; k += 2, now = P - now) {
        xorsum ^= 1ll * now * binom(k, k / 2) % P;
      }
      printf("%d\n", xorsum);
      continue;
    }
    int a = -1ll * c * c % P * power(1ll * (c + 1) * (c + 1) % P, P - 2) % P;
    a = (a + P) % P;
    int xorsum = 0;
    q[0] = 1;
    q[1] = 2;
    int pw = 1;
    for (int i = 1; i <= n; ++i) {
      pw = 1ll * pw * (c + 1) % P;
      if (i == 1) q[i] = 2;
      else q[i] = ((4ll * i - 2) * q[i - 1] + 4ll * a * (i - 1) % P * q[i - 2]) % P * inv[i] % P;
      if (q[i] < 0) q[i] += P;
      xorsum ^= 1ll * q[i] * pw % P;
    }
    printf("%d\n", xorsum);
  }
}