#include<stdio.h>
#include<cstring>
#define N 500005
using namespace std;
int test,i,j,k,l,s,n,m,f[N][11],last[N],next[N],to[N],tot;
int a,bb,x,q[N],r,fa[N],d[N][11],ans[N],g[N];
inline void build() {
    int l=0,r=1; 
    q[1]=1;
    while (l<r) 
    for (int i=last[q[++l]];i;i=next[i]) 
    fa[q[++r]=to[i]]=k;    
}
inline void add(int o,int p) {
    next[++tot]=last[o]; 
    last[o]=tot; 
    to[tot]=p;
}
inline int in() {
    char c=getchar();
    int s=0;
    while (c<'0'||c>'9') c=getchar();
    while (c>='0'&&c<='9') s=s*10+c-48,c=getchar();
    return s;
}        
int main() {
    scanf("%d",&test);
    while (test--) {
        scanf("%d%d%d%d",&n,&m,&a,&bb); tot=0;
        for (i=1;i<=n;i++)
    for (j=0;j<=m;j++) 
    f[i][j]=d[i][j]=0; 
        for (i=1;i<=n;i++) {
        f[i][0]=1;
        last[i]=ans[i]=0;
    }
        for (i=2;i<=n;i++) {
        x=(1ll*a*i+bb)%(i-1)+1;
        add(x,i);
    }
    build();
        for (i=n;i;i--) 
    for (j=last[q[i]];j;j=next[j]) 
    for (k=0;k<m;k++) 
    f[q[i]][k+1]=f[q[i]][k+1]+f[to[j]][k];
        for (i=1;i<=n;i++) 
    for (j=last[q[i]];j;j=next[j]) {
            for (k=1;k<m;k++) 
    d[to[j]][k+1]=d[to[j]][k+1]+(f[q[i]][k]-f[to[j]][k-1])+d[q[i]][k];
            d[to[j]][1]=d[to[j]][1]+f[q[i]][0]+d[q[i]][0];
        }
        int gt=0;
        for (i=n;i;i--) 
    for (k=0;k<=m;k++) 
    ans[i]=ans[i]+f[i][k]+d[i][k];
        for (i=1;i<=n;i++) 
    gt^=ans[i];
        printf("%d\n",gt);
    }
}