#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const long long INF=0x3f3f3f3f;
long long seed;
long long a[1000005][5];
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() {
    long long cas,n,i,j,s,l,r,t,ans;
    cin>>cas;
    while(cas--){
        cin>>n>>seed;
    for(i=0;i<n;i++){
    a[i][0]=rand(-1000000000, 1000000000);
    a[i][1]=rand(-1000000000, 1000000000);
    }
    ans=0;
    for(s=0;s<(1<<2);s++){
        l=INF,r=-INF;
        for(i=0;i<n;i++){
            t=0;
            for(j=0;j<2;j++){
                if((1<<j)&s)
                t+=a[i][j];
                else
                t-=a[i][j];
            }
            l=min(l,t);
            r=max(r,t);
        }
        ans=max(ans,r-l);
    }
    printf("%I64d\n",ans);
    }
    return 0;
}