#pragma comment(linker, "/STACK:102400000,102400000") 
#include<cstdio>
#define N 500005
#define M 11
using namespace std;
int Go[N],Next[N],End[N],cnt;
int g[N][M],h[N][M],f[N],n,L,A,B,i,T,ans;
void DFS1(int x){    
    for (int i=1;i<=L;i++) g[x][i]=0;g[x][0]=1;
    for (int i=End[x],y;i;i=Next[i]){
        DFS1(y=Go[i]);
        for (int j=1;j<=L;j++)
            g[x][j]+=g[y][j-1];
  }
}
void DFS2(int x){
    int sum=0;
    if (x>1) for (int i=1;i<=L;i++)
        h[x][i]=h[f[x]][i-1]+g[f[x]][i-1]-(i>1?g[x][i-2]:0);
    for (int i=0;i<=L;i++)
        sum+=g[x][i]+h[x][i];
    //printf("%d %d\n",x,sum);
    ans^=sum;
  for (int i=End[x];i;i=Next[i])
        DFS2(Go[i]);
}
void add(int u,int v){
    Go[++cnt]=v;Next[cnt]=End[u];End[u]=cnt;
}
int main(){
    scanf("%d",&T);
    while (T--){
      scanf("%d%d%d%d",&n,&L,&A,&B);
        for (i=1;i<=n;i++) End[i]=0;f[1]=0;cnt=0;
        for (i=2;i<=n;i++)
            f[i]=(1ll*A*i+B)%(i-1)+1,add(f[i],i);
            
        /*scanf("%d%d",&n,&L);
        for (i=1;i<=n;i++) End[i]=0;cnt=0;
        for (i=2;i<=n;i++)
            scanf("%d",&f[i]),add(f[i],i);*/
        DFS1(1);ans=0;
        for (i=1;i<=L;i++) h[1][i]=0;
        DFS2(1);
        printf("%d\n",ans);
  }  
}