#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <queue>
#include <typeinfo>
#include <fstream>
#include <map>
#include <iomanip>
typedef long long ll;
using namespace std;
//freopen("D.in","r",stdin);
//freopen("D.out","w",stdout);
#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)
#define dbg(a) cout<<a<<endl
#define clr(a) memset(a,0,sizeof(a))
#define maxn 1000010
#define mod 1000000007
#define eps 1e-9
#define inf 0x7fffffff
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);
}
ll x[maxn],y[maxn];
int main()
{
    int T;
    cin>>T;
    while (T--)
    {
        int n;
        cin >> n >> seed;
        for (int i = 0; i < n; i++)
            x[i] = rand(-1000000000, 1000000000),
            y[i] = rand(-1000000000, 1000000000);
        ll maxx,minn,maxa,mina;
        int i;
        maxx = x[0] + y[0];
        minn = maxx;
        maxa = x[0] - y[0];
        mina = maxa;
        for (i=0;i<n;i++)
        {
            maxx=max(maxx,x[i]+y[i]);
            minn=min(minn,x[i]+y[i]);
            maxa=max(maxa,x[i]-y[i]);
            mina=min(mina,x[i]-y[i]);
        }
        cout<<max(maxx-minn,maxa-mina)<<endl;
    }
    return 0;
}