#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#include <deque>
#include <cstring>
#include <functional>
#include <climits>
#include <list>
#include <ctime>
#include <complex>

#define F1(x,y,z) for(int x=y;x<z;x++)
#define F2(x,y,z) for(int x=y;x<=z;x++)
#define F3(x,y,z) for(int x=y;x>z;x--)
#define F4(x,y,z) for(int x=y;x>=z;x--)
#define pb push_back
#define LL long long
#define co complex<double>
 
#define MAX 100005
#define AMAX 1500
#define MOD 1000000007

#define f(c,d) ((1<<(c))*(d))

using namespace std;

int t,n;
LL z[4],x,y;

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(){
    scanf("%d",&t);
    while(t--){
        z[0]=z[1]=LLONG_MIN;
        z[2]=z[3]=LLONG_MAX;
        scanf("%d%I64d",&n,&seed);
        for (int i = 0; i < n; i++){
            x = rand(-1000000000, 1000000000),
            y = rand(-1000000000, 1000000000);
            z[0]=max(z[0],x+y);
            z[1]=max(z[1],x-y);
            z[2]=min(z[2],x+y);
            z[3]=min(z[3],x-y);
        }
        printf("%I64d\n",max(z[0]-z[2],z[1]-z[3]));
    }
    //system("pause");
}