#include<cstdio>
#include<cstring>
#include<algorithm>
typedef long long ll;
using namespace std;
int cas,n,m,s;
ll seed,mx,mi,Mx,Mi;
ll x[1000010],y[1000010],X[1000010],Y[1000010];
inline ll rand(ll l,ll r){
    static ll mo=1e9+7,g=78125;
    return l+((seed*=g)%=mo)%(r-l+1);
}
int main(){
    scanf("%d",&cas);
    while (cas--){
        scanf("%d%I64d",&n,&seed);
        for (int i=1;i<=n;i++)x[i]=rand(-1000000000,1000000000),y[i]=rand(-1000000000,1000000000);
        for (int i=1;i<=n;i++)X[i]=x[i]+y[i],Y[i]=x[i]-y[i];
        Mi=mi=100000000000000000;
        Mx=mx=-100000000000000000;
        for (int i=1;i<=n;i++){
            if (X[i]>mx)mx=X[i];
            if (X[i]<mi)mi=X[i];
            if (Y[i]>Mx)Mx=Y[i];
            if (Y[i]<Mi)Mi=Y[i];
        }
        printf("%I64d\n",max(mx-mi,Mx-Mi));
    }
}