#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<stack>
#define M 500005
using namespace std;
vector<int>edge[M];
int dp[M][11],dp1[M][11];
int st=0,max_dep=0;
void dfs(int x,int fa,int K){
    dp[x][0]=1;
    int j,k;
    int cnt=0,tot=0;
    for(j=0;j<edge[x].size();j++){
        int to=edge[x][j];
        if(to==fa) continue;
        dfs(to,x,K);
        for(k=1;k<=K;k++) dp[x][k]+=dp[to][k-1];
    }
}
void dfs1(int x,int fa,int K){
    int j,k;
    int back[11];
    for(j=0;j<edge[x].size();j++){
        int to=edge[x][j];
        if(to==fa) continue;
        for(k=K;k>=2;k--) dp[to][k]+=dp[x][k-1]-dp[to][k-2];
        dp[to][1]++;
        dfs1(to,x,K);
    }
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        memset(dp,0,sizeof(dp));
        memset(dp1,0,sizeof(dp1));
        int n,k,j,K,a,b;
        scanf("%d%d%d%d",&n,&K,&a,&b);
        for(j=1;j<=n;j++) edge[j].clear();
        for(j=2;j<=n;j++){
            int fa=(1LL*a*j+b)%(j-1LL)+1;
            //printf("%d %d\n",j,fa);
            edge[j].push_back(fa);
            edge[fa].push_back(j);
        }
        dfs(1,0,K);
        dfs1(1,0,K);
        //printf("dp = %d\n",dp[1][1]);
        int ans=0;
        for(j=1;j<=n;j++){
            int now=0;
            for(k=0;k<=K;k++){
                now+=dp[j][k];
            }
            //printf("%d %d\n",j,now);
            ans^=now;
        }
        printf("%d\n",ans);
    }
    //system("pause");
    return 0;
}