#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long LL;

const int maxn=500010;
const int maxk=15;

struct edge{
        int to,next;
}e[maxn*2];
int n,k,e_num=0,head[maxn],fa[maxn],f[maxn][maxk],g[maxn][maxk];

void add_edge(int u,int v){
        e[++e_num]=(edge){v,head[u]};
        head[u]=e_num;
}

void dfs1(int a){
        f[a][0]=1;
        for(int i=head[a]; i; i=e[i].next)
                if(e[i].to!=fa[a]){
                        dfs1(e[i].to);
                        for(int j=1; j<=k; ++j)
                                f[a][j]+=f[e[i].to][j-1];
                }
}

void dfs2(int a){
        g[a][0]=1;
        if(a==1){
                for(int j=1; j<=k; ++j)
                        g[a][j]=f[a][j];
        }
        else{
        for(int j=1; j<=k; ++j)
                g[a][j]=f[a][j]+g[fa[a]][j-1]-(j>=2 ? f[a][j-2] : 0);
        }
        for(int i=head[a]; i; i=e[i].next)
                if(e[i].to!=fa[a]) dfs2(e[i].to);
}

void work(){
        e_num=0;
        int a,b;
        scanf("%d%d%d%d",&n,&k,&a,&b);
        for(int i=0; i<=n; ++i){
                head[i]=0;
                for(int j=0; j<=k; ++j)
                        g[i][j]=f[i][j]=0;
        }
        fa[1]=0;
        for(int i=2; i<=n; ++i){
                fa[i]=(int) (((LL)a*(LL)i+b)%((LL)i-1)+1);
                add_edge(fa[i],i);
                add_edge(i,fa[i]);
        }
        dfs1(1);
        dfs2(1);
        for(int i=1; i<=n; ++i)
                for(int j=1; j<=k; ++j){
                        
                        g[i][j]+=g[i][j-1];
                }
        LL ans=0;
        for(int i=1; i<=n; ++i)
                ans=ans^g[i][k];
        printf("%I64d\n",ans);
}

int main(){
        int kase;
        scanf("%d",&kase);
        while(kase--) work();
        return 0;
}