#include<iostream>
#include<cstdio>
#include<cstring>
#include<string.h>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
#include<stdlib.h>
#include<time.h>
#include<stack>
#include<set>
using namespace std;
#define rep0(i,l,r) for(int i = (l);i < (r);i++)
#define rep1(i,l,r) for(int i = (l);i <= (r);i++)
#define rep_0(i,r,l) for(int i = (r);i > (l);i--)
#define rep_1(i,r,l) for(int i = (r);i >= (l);i--)
#define MS0(a) memset(a,0,sizeof(a))
#define MS1(a) memset(a,-1,sizeof(a))
typedef __int64 ll;
template<typename T>
void read1(T &m)
{
    T x=0,f=1;char ch=getchar();
    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
    m = x*f;
}
template<typename T>
void read2(T &a,T &b){read1(a);read1(b);}
template<typename T>
void read3(T &a,T &b,T &c){read1(a);read1(b);read1(c);}
template<typename T>
void out(T a)
{
    if(a>9) out(a/10);
    putchar(a%10+‘0‘);
}
ll n,seed;
inline ll rand(ll l, ll r) {
    static ll mo=1e9+7, g=78125;
    return l+((seed*=g)%=mo)%(r-l+1);
}
const ll inf = 0x3f3f3f3f3f3f3f3fLL;
int main()
{
    int T;
    read1(T);
    while(T--){
        read2(n,seed);
        ll mn0 = inf,mn1 = -inf,mx0 = inf,mx1 = -inf,x,y,ans;
        rep0(i,0,n){
            x = rand(-1000000000, 1000000000);
            y = rand(-1000000000, 1000000000);
            ll tmp = x + y,temp = x - y;
            mn0 = min(mn0,tmp);mn1 = max(mn1,tmp);
            mx0 = min(mx0,temp);mx1 = max(mx1,temp);
        }
        ans = max(mn1 - mn0,mx1 - mx0);
        out(ans);puts("");
    }
    return 0;
}