#pragma comment(linker, "/STACK:102400000,102400000")

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>

#define MAX 500010
#define X first
#define Y second

using namespace std;

typedef long long i64;
typedef pair<int, int> Pii;

int dp[MAX][12], cur[MAX][12];

struct Edge {
  int u, v, nxt;

  Edge() {}
  Edge(int _u, int _v, int _nxt) : u(_u), v(_v), nxt(_nxt) {}
} edge[MAX << 1];

int head[MAX], nEdge;

inline void Init(int n) {
  fill(head, head + n, -1);
  nEdge = 0;
}

inline void AddEdge(int a, int b) {
  edge[nEdge] = Edge(a, b, head[a]); head[a] = nEdge++;
  edge[nEdge] = Edge(b, a, head[b]); head[b] = nEdge++;
}

void Dfs1(int x, int pre, int k) {
  dp[x][0] = 1;
  for (int i = head[x]; ~i; i = edge[i].nxt) {
    int y = edge[i].v;
    if (y != pre) {
      Dfs1(y, x, k);
      for (int j = 1; j <= k; ++j) {
        dp[x][j] += dp[y][j - 1];
      }
    }
  }
}

void Dfs2(int x, int pre, int k, int& ans) {
  int sum = 0;
  for (int i = 0; i <= k; ++i) {
    sum += dp[x][i] + cur[x][i];
  }
  ans ^= sum;
  for (int i = head[x]; ~i; i = edge[i].nxt) {
    int y = edge[i].v;
    if (y != pre) {
      cur[y][1] = 1;
      for (int j = 1; j < k; ++j) {
        cur[y][j + 1] += cur[x][j] + dp[x][j] - dp[y][j - 1];
      }
      Dfs2(y, x, k, ans);
    }
  }
}

int Solve(int n, int k) {
  memset(dp, 0, sizeof(dp));
  Dfs1(0, -1, k);
  memset(cur, 0, sizeof(cur));
  int ret = 0;
  Dfs2(0, -1, k, ret);
  return ret;
}

int main() {
  int t, n, k, a, b;
  scanf("%d", &t);
  while (t--) {
    scanf("%d%d%d%d", &n, &k, &a, &b);
    Init(n);
    for (int i = 2; i <= n; ++i) {
      int u = ((i64)a * (i64)i + b) % (i - 1) + 1;
      AddEdge(i - 1, u - 1);
    }
    printf("%d\n", Solve(n, k));
  }
  return 0;
}