/* ***********************************************
Author        :kuangbin
Created Time  :2015/12/5 19:24:06
File Name     :F:\ACM\2015ACM\BestCoder\BC65\D.cpp
************************************************ */

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;

const int MAXN = 500010;
struct Edge {
    int to, next;
}edge[MAXN];
int head[MAXN],tot;
void init() {
    tot = 0;
    memset(head,-1,sizeof(head));
}
void addedge(int u, int v) {
    edge[tot].to = v;
    edge[tot].next = head[u];
    head[u] = tot++;
}
int fa[MAXN];
int dp[MAXN][11];
int q[MAXN];

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int T;
    scanf("%d",&T);
    while(T--) {
        int n,k,A,B;
        scanf("%d%d%d%d",&n, &k, &A,&B);
        fa[1] = 0;
        for(int i = 2;i <= n;i++)
            fa[i] = ((long long)A*i+B)%(i-1)+1;
        init();
        for(int i = 2;i <= n;i++)addedge(fa[i], i);
        memset(dp, 0, sizeof(dp));
        int l,r;
        q[l=r=1] = 1;
        while(l <= r) {
            int u = q[l++];
            for(int i = head[u];i != -1;i = edge[i].next) {
                int v = edge[i].to;
                q[++r] = v;
            }
        }
        for(int j = n;j >= 1;j--) {
            int u = q[j];
            dp[u][0] = 1;
            for(int i = head[u];i != -1;i = edge[i].next) {
                int v = edge[i].to;
                for(int k = 1;k <= 10;k++) {
                    dp[u][k] += dp[v][k-1];
                }
            }
        }
        for(int j = 1;j <= n;j++) {
            int u = q[j];
            if(fa[u] == 0)continue;
            int v = fa[u];
            for(int k = 10;k >= 1;k--) {
                dp[u][k] += dp[v][k-1];
                if(k > 1)dp[u][k] -= dp[u][k-2];
            }
        }
        int ans = 0;
        for(int i = 1;i <= n;i++) {
            int tmp = 0;
            for(int j = 0;j <= k;j++)tmp += dp[i][j];
            ans ^= tmp;
        }
        printf("%d\n",ans);
    }
    return 0;
}