#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
typedef  long long ll;
 ll n ,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);
}
const int  maxn = 1000000 + 10;
// ...

ll x[maxn];
ll y[maxn];


int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%I64d%I64d",&n,&seed);
        ll mi1= 0;
        ll mi2= 0;
        ll mi3= 0;
        ll mi4= 0;
        ll m1 = -2111111111;
        ll m2 = 2111111111;
        ll m3 = -2111111111;
        ll m4 = -2111111111;
        for (int  i = 0; i < n; i++){
            x[i] = rand(-1000000000, 1000000000),
            y[i] = rand(-1000000000, 1000000000);
            if(x[i] + y[i] > m1) {
                m1 = x[i] + y[i];
                mi1 = i;
            }
            if(x[i] + y[i] <m2){
                m2 = x[i] + y[i];mi2 = i;
            }
          /*  if(-x[i] + -y[i] >m5){
                m2 = -x[i] + -y[i];mi2 = i;
            }
             if(-x[i] + -y[i] <m5){
                m2 = -x[i] + -y[i];mi2 = i;
            }*/
            if(x[i]  - y[i] > m3){
                m3 = x[i] - y[i];mi3 = i;
            }
             if(y[i]  -x[i] >m4){
                m4 = y[i] - x[i];mi4 = i;
            }
        }
        ll ans1 = (abs(x[mi1] - x[mi2])) + abs(y[mi1]-y[mi2]);
        ll ans2 = (abs(x[mi3] - x[mi4])) + abs(y[mi3]-y[mi4]);

        ll ans = max(ans1,ans2);
        printf("%I64d\n",ans);
    }
    return 0;
}