#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#define N 11000000
#define mod 1000000007
using namespace std;
typedef long long ll;
long long seed;
int rand(int l, int r) {
    static long long mo=1e9+7, g=78125;
    return l+((seed*=g)%=mo)%(r-l+1);
}
int a[N],s[N];

int main()
{
    int c,T,n,q,i,j,k,x,y,ans;
    cin>>T;
    for(c=1;c<=T;c++)
    {
        cin>>n>>q>>seed;
        int sum=rand(q, 10000000);
        for(i=1; i<=n; i++) {
            a[i]=rand(0, sum/(n-i+1));
            sum-=a[i];
        }
        a[rand(1, n)]+=sum;
        memset(s,0,sizeof(s));
        for(i=1;i<=n;i++)
        {
            s[a[i]]++;
        }
        for(i=10000000;i>0;i--)
        {
            while(s[i]&&q)
                s[i]--,s[i-1]++,q--;
            if(!q)
                break;
        }
        int cnt=0;
        for(j=n,ans=0;j>=1;j--)
        {
            if(a[j]<i)
            ans^=(a[j]+j);
            else if(a[j]>=i&&cnt<s[i])
            ans^=(i+j),cnt++;
            else
            ans^=(i-1+j);
        }
        printf("%d\n",ans);
    }
    return 0;
}