#include<stdio.h>
#include<iostream>
#include<vector>
#include<string.h>
#include<set>
#include<string>
#include<map>
#include<algorithm>
#include<queue>
using namespace std;
__int64 seed;
inline __int64 rand(__int64 l, __int64 r) {
    static __int64 mo=1e9+7, g=78125;
    return l+((seed*=g)%=mo)%(r-l+1);
}
int n;

__int64 p[1000005][2];
__int64 inf=1000000000*100;

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%I64d",&n,&seed);
        for(int i=0;i<n;i++)
        {
            p[i][0]=rand(-1000000000, 1000000000);
            p[i][1]=rand(-1000000000, 1000000000);
        }
        __int64 ans = 0, mi, mx, t;  
        for (int s=0; s<(1<<2); s++) {  
            mi = inf, mx = -inf;  
            for (int i=0; i<n; i++) {  
                t = 0;  
                for (int j=0; j<2; j++)  
                    if ((1<<j) & s) t += p[i][j];  
                    else t -= p[i][j];  
                mi = min(mi, t);  
                mx = max(mx, t);  
            }  
            ans = max(ans, mx-mi);  
        }  
        printf("%I64d\n", ans);   
    }
    return 0;
}