// ━━━━━━神兽出没━━━━━━
// ━━━━ mythical creatures ━━
//      ┏┓       ┏┓
//     ┏┛┻━━━━━━━┛┻┓
//     ┃           ┃
//     ┃     ━     ┃
//     ━   ┃
//     ┃           ┃
//     ┃    ┻      ┃
//     ┃           ┃
//     ┗━┓       ┏━┛
//       ┃       ┃
//       ┃       ┃
//       ┃       ┗━━━┓
//       ┃           ┣┓
//       ┃           ┏┛
//       ┗┓┓┏━━━━━┳┓┏┛
//        ┃┫┫     ┃┫┫
//        ┗┻┛     ┗┻┛
//
// ━━━━━━感觉萌萌哒━━━━━━
// ━━━━━━feel lovely━━━━━

// Author        : lkdmhy 



#pragma comment(linker, "/STACK:1677721600")
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <bitset>
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
#define pf printf
#define sf scanf
#define mem0(a) memset(a,0,sizeof(a))
#define mem_1(a) memset(a,-1,sizeof(a))
#define FIN freopen("in.txt", "r", stdin)
#define FOUT freopen("out.txt", "w", stdout)

template <class T>
inline bool in(T &ret) {
    char c; int sgn;
    if (c=getchar(),c==EOF) return 0;
    while (c!='-'&&(c<'0'||c>'9')) c=getchar();
    sgn=(c=='-')?-1:1;
    ret=(c=='-')?0:(c-'0');
    while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
    ret*=sgn;
    return 1;
}
template <class T>
inline void out(T x) {
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9) out(x/10);
    putchar(x%10+'0');
}

template<class T> T MAX(T a, T b) { return a > b ? a : b; }
template<class T> T MIN(T a, T b) { return a < b ? a : b; }
template<class T> T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }
template<class T> T LCM(T a, T b) { return a / GCD(a,b) * b;    }

typedef long long LL;
typedef unsigned long long ULL;

const int maxn = 1000000+10;
const int dem = 2;  //维数
const double INF = (1e200);

int T,n;

struct Point{
    double  x[dem];
}p[maxn];

double minx[1<<dem], maxx[1<<dem];

double 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;
            double 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;
        }
    }

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

    return ans;
}

long long seed;
 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(){
    cin>>T;
    while(T--) {
        cin >> n >> seed;
        
        for(int i=0; i<n; i++) {
            for(int j=0; j<dem; j++) {
                p[i].x[j]=rand(-1000000000, 1000000000);
            }
        }
        printf("%.0f\n", solve());
    }

    return 0;
}

/*



*/