#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <functional>
#include <set>
#include <ctime>
using namespace std;

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 t;
    cin >> t;
    while(t--){
        int n;
        cin >> n >> seed;
        vector<long long> x(n),y(n);

        for (int i = 0; i < n; i++)
            x[i] = rand(-1000000000, 1000000000),
            y[i] = rand(-1000000000, 1000000000);
        
        long long xpy_max = -(1LL<<50);
        long long xpy_min = 1LL<<50;
        long long xmy_max = -(1LL<<50);
        long long xmy_min = 1LL<<50;

        for(int i=0; i<n; i++){
            xpy_max = max(xpy_max, x[i]+y[i]);
            xpy_min = min(xpy_min, x[i]+y[i]);

            xmy_max = max(xmy_max, x[i]-y[i]);
            xmy_min = min(xmy_min, x[i]-y[i]);
        }

        long long ans = max(max(max(xpy_max - xpy_min,
                            -xmy_min + xmy_max),
                             xmy_max - xmy_min),
                            -xpy_min + xpy_max);

        cout << ans << endl;
    }
    return 0;
}