#pragma comment(linker, "/STACK:102400000,102400000") 
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 531072
using namespace std;
typedef long long ll;
int fa[N];
int fx[N][11],fy[N][11],k;
int next[N],to[N],head[N],ce;
void init(int n)
{
    memset(head,0,sizeof(int)*(n+1));
    ce=0;
}
void add(int x,int y)
{
    to[++ce]=y;
    next[ce]=head[x];
    head[x]=ce;
}
void dfs1(int x)
{
    int i,j;
    for(i=1;i<=k;i++)
        fx[x][i]=0;
    fx[x][0]=1;
    for(i=head[x];i;i=next[i])
    {
        dfs1(to[i]);
        for(j=0;j<k;j++)
            fx[x][j+1]+=fx[to[i]][j];
    }
}
void dfs2(int x)
{
    int i,j;
    fy[x][0]=0;
    if(x!=1)
    for(i=0;i<k;i++)
        fy[x][i+1]=fy[fa[x]][i]+fx[fa[x]][i]-(i-1>=0?fx[x][i-1]:0);
    for(i=head[x];i;i=next[i])
    {
        dfs2(to[i]);
    }
}
int main()
{
    int c,T,n,a,b,i,j,temp,ans;
    scanf("%d",&T);
    for(c=1;c<=T;c++)
    {
        scanf("%d%d%d%d",&n,&k,&a,&b);
        init(n);
        for(i=2;i<=n;i++)
        {
            fa[i]=((ll)a*i+b)%(i-1)+1;
            add(fa[i],i);
        }
        dfs1(1);
        dfs2(1);
        for(i=1,ans=0;i<=n;i++)
        {
            for(j=0,temp=0;j<=k;j++)
            {
                temp+=fx[i][j];
                temp+=fy[i][j];
            }
            ans^=temp;
        }
        printf("%d\n",ans);
    }
    return 0;
}