#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;
const int N=5E5+5;
const int K=12;
int n,f[N][K],k,ans,T,A,B,x,g[N];
vector <int> G[N];

void dfs(int x)
{
    int y;
    f[x][0]=1;
    for (int i=0;i<G[x].size();i++) 
    {
        dfs(y=G[x][i]);
        for (int j=1;j<=k;j++) f[x][j]+=f[y][j-1];
    }
}

void find(int x)
{
    int y,sum=0;
    for (int i=0;i<=k;i++) sum+=f[x][i];
    ans^=sum; g[x]=sum;
    for (int i=0;i<G[x].size();i++) 
    {
        y=G[x][i]; 
        for (int j=k;j>=2;j--) f[y][j]+=f[x][j-1]-f[y][j-2];
        f[y][1]++;
        find(y);
    }
}

int main()
{
    cin>>T;
    while (T--)
    {
        memset(f,0,sizeof(f));
        cin>>n>>k>>A>>B;
        for (int i=1;i<=n;i++) G[i].clear();
        for (int i=2;i<=n;i++) 
        {
            x=((long long)A*i+B)%(i-1)+1;
        //    cerr<<x<<" "<<i<<endl;
            G[x].push_back(i);
        }
        dfs(1);
        ans=0; find(1);
        cout<<ans<<endl;
    }
}