#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>

#define ll long long
#define inf 1000000001
#define eps 1e-10
#define md
#define N 1000010
using namespace std;

int X[N],Y[N];
long long seed;
inline long long rand(long long l, long long r) {
    static long long mo=1e9+7, g=78125;
    return l+((seed*=g)%=mo)%(r-l+1);
}

// ...

int main()
{
    int tt,n;
    scanf("%d",&tt);
    while (tt--)
    {
        scanf("%d%I64d",&n,&seed);
        for (int i = 1; i <= n; i++)
                X[i] = rand(-1000000000, 1000000000),
            Y[i] = rand(-1000000000, 1000000000);
        ll mx1=-inf,mx2=-inf,mn1=inf,mn2=inf;
        for (int i=1;i<=n;i++)
        {
            ll t1=X[i]+Y[i],t2=X[i]-Y[i];
            mx1=max(mx1,t1); mx2=max(mx2,t2);
            mn1=min(mn1,t1); mn2=min(mn2,t2);
        }
        printf("%I64d\n",max(mx1-mn1,mx2-mn2));
    }
    return 0;
}