#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,k,f[500005],s[500005][11],ans[500005];
long long A,B;
int main(){
    int tt;scanf("%d",&tt);
    for (;tt--;){
        scanf("%d%d%d%d",&n,&k,&A,&B);
        for (int i=1;i<=n;i++) ans[i]=0;
        for (int i=1;i<=n;i++)
            for (int j=0;j<=k;j++)
                s[i][j]=0;
        for (int i=2;i<=n;i++) f[i]=(1ll*A*i+B)%((long long)i-1ll)+1;
        for (int i=1;i<=n;i++)
            for (int j=0,p=i;j<=k&&p;j++,p=f[p])
                s[p][j]++;
        for (int i=1;i<=n;i++)
            for (int j=1;j<=k;j++)
                s[i][j]+=s[i][j-1];
        for (int i=1;i<=n;i++)
            for (int j=0,p=i;j<=k&&p;j++,p=f[p]){
                ans[i]+=s[p][k-j];
                if (j<k-1&&p!=1) ans[i]-=s[p][k-j-2];
            }
        int aa=0;
        for (int i=1;i<=n;i++) aa^=ans[i];
        printf("%d\n",aa);
    }
}