//BestCoder #62 1003
//write by Lone Wolf in 2015.11.14
#pragma comment(linker, "/STACK:102400000,102400000")
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#define PI (acos(-1.0))
#define lowbit(x) (x&(-x))
#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)
typedef long long LL;
using namespace std;
const int MOD=1000000007;
const int INF=0x3f3f3f3f;
const int N=20000010;
const int M=100010;
const int Mat=110;
typedef double Matrix[Mat][Mat];
const double eps=1e-10;
inline int readint()
{
    char c=getchar();
    while (c<'0'||c>'9') c=getchar();
    int x=0;
    while ('0'<=c&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x;
}
int buf[10];
inline void writeint(int i)
{
    int p=0;
    if (i==0) p++;
    else while (i)
    {
        buf[p++]=i%10;
        i/=10;
    }
    for (int j=p-1;j>=0;j--) putchar('0'+buf[j]);
}
int n,m;
LL q;
long long seed;
LL a[N];
int rand(int l, int r)
{
    static long long mo=1e9+7, g=78125;
    return l+((seed*=g)%=mo)%(r-l+1);
}
void init()
{
    int sum=rand(q, 10000000);
    for(int i=1; i<=n; i++) {
        a[i]=rand(0, sum/(n-i+1));
        sum-=a[i];
    }
    a[rand(1, n)]+=sum;
}
LL func(int x)
{
    LL ret=0;
    for (int i=1;i<=n;i++)
    {
        if (a[i]>x) ret+=a[i]-x;
    }
    return ret;
}
int f()
{
    int l=0;
    int r=m+1;
    int mid;
    LL ret;
    while (l+1<r)
    {
        mid=l+r>>1;
        ret=func(mid);
        if (ret>=q) l=mid;
        else r=mid;
    }
    return l+1;
}
void solve()
{
    int i,j,k;
    LL ans;
    scanf("%d%I64d%I64d",&n,&q,&seed);
    init();
    if (q>0)
    {
        m=a[1];
        for (i=2;i<=n;i++)
        {
            if (a[i]>m) m=a[i];
        }
        ans=f();
        for (i=1;i<=n;i++)
        {
            if (a[i]>ans)
            {
                q=q-(a[i]-ans);
                a[i]=ans;
            }
        }
        if (q>0)
        {
            for (i=1;i<=n;i++)
            {
                if (a[i]==ans&&q>0)
                {
                    a[i]--;
                    q--;
                }
                if (q==0) break;
            }
        }
    }
    ans=0;
    for (i=1;i<=n;i++)
    {
        ans=ans^(a[i]+i);
    }
    cout<<ans<<endl;
    return;
}
int main()
{
    //freopen("test.in","r",stdin);
    //freopen("test.out","w",stdout);
    int i,T=1;
    scanf("%d",&T);
    for (i=1;i<=T;i++)
    {
        solve();
    }
    return 0;
}