#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 1100000
int n,k,a,b;
int tot,T;
int head[N],nex[N],to[N],ans[N];
int f[N][11],g[N][11];
void add(int x,int y)
{
    tot++;
    nex[tot]=head[x];
    head[x]=tot;
    to[tot]=y;
}
void dfs1(int x,int fa)
{
    f[x][0]=1;
    for(int i=head[x];i;i=nex[i])
    if(to[i]!=fa)
    {
        dfs1(to[i],x);
        for(int j=1;j<=k;j++)
        f[x][j]+=f[to[i]][j-1];
    }
}
void dfs2(int x,int fa)
{
    if(x!=1)
    for(int i=1;i<=k;i++)
    {    
        g[x][i]=g[fa][i-1]+f[fa][i-1];
        if(i>=2&&x!=1)
        g[x][i]-=f[x][i-2];
    }
    for(int i=head[x];i;i=nex[i])
    if(to[i]!=fa)
    dfs2(to[i],x);
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        tot=1;
        scanf("%d%d%d%d",&n,&k,&a,&b);
        for(int i=1;i<=n;i++)
        {
            head[i]=0;
            ans[i]=0;
        }
        for(int i=1;i<=n;i++)
        for(int j=0;j<=k;j++)
        {
            f[i][j]=0;
            g[i][j]=0;
        }
        for(int i=2;i<=n;i++)
        {
    int t=(a+b)%(i-1)+1;
            add(i,t);
            add(t,i);
        }
        dfs1(1,0);
        dfs2(1,0);
        int res=0;
        for(int i=1;i<=n;i++)
        {    
            ans[i]=1;
            for(int j=1;j<=k;j++)
            {    
                ans[i]+=f[i][j]+g[i][j];
            }
            res^=ans[i];
        }
        printf("%d\n",res);
    }
    return 0;
}