#include<algorithm>
#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
#define dem 2
#define maxn 1000005
using namespace std;
long long seed;int n;
int minx[1<<dem], maxx[1<<dem];
long long INF = 2000000000;
struct Point{int x[2];}p[maxn];
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 solve() {
    int tmp = 1<<dem;
    for(int i=0; i<tmp; i++) {
        minx[i] = INF;
        maxx[i] = -INF;
    }
    for(int i=0; i<n; i++) {
        for(int j=0; j<tmp; j++) {
            int t = j;
            int s = 0;
            for(int k=0; k<dem; k++) {
                if(t & 1) s += p[i].x[k];
                else s -= p[i].x[k];
                t >>= 1;
            }
            if(maxx[j] < s) maxx[j] = s;
            if(minx[j] > s) minx[j] = s;
        }
    }

    int ans = -INF;
    for(int i=0; i<tmp; i++) {
        if(maxx[i] - minx[i] > ans)
            ans = maxx[i] - minx[i];
    }
    return ans;
}

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        cin >> n >> seed;
        for (int i = 0; i < n; i++)
            p[i].x[0] = rand(-1000000000, 1000000000),
            p[i].x[1] = rand(-1000000000, 1000000000);
        cout<<solve()<<endl;
    }
    return 0;
}