#include<cstdio>
#include<iostream>
#include<cstring>
#define INF 100000000000LL
using namespace std;
int T;
long long n,seed;
long long x[1000005],y[1000005];
long long a[1000005],b[1000005];
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);
}
void work()
{
    scanf("%I64d%I64d",&n,&seed);
    for (long long i = 1; i <=n; i++)
        x[i] = rand(-1000000000LL, 1000000000LL),
        y[i] = rand(-1000000000LL, 1000000000LL);
    for (int i = 1; i <= n; i++)
            a[i] = x[i] + y[i], b[i] = x[i] - y[i];
        long long mxx = -INF, mnx = INF, mxy = -INF, mny = INF;
        for (int i = 1; i <= n; i++) {
            mxx = max(mxx, a[i]);
            mnx = min(mnx, a[i]);
            mxy = max(mxy, b[i]);
            mny = min(mny, b[i]);
        }
        printf("%I64d\n", max(mxx - mnx, mxy - mny));
}
int main()
{
    scanf("%d",&T);
    while(T--)
        work();
    return 0;
}