#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
#include <vector>
#include <iostream>
#include <map>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 1e6 + 10;
ll x[N], y[N];




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 n;
int main()
{
    int _; cin >> _;
    while(_ --)
    {
        cin >> n >> seed;
        for (int i = 0; i < n; i++)
            x[i] = rand(-1000000000, 1000000000),
                   y[i] = rand(-1000000000, 1000000000);
        ll ans = -INF, tmp, mi = INF, mx = -INF;
        for(int i = 0; i < n; ++i)
        {
            tmp = x[i] + y[i];
            mx = max(mx, tmp);
            mi = min(mi, tmp);
        }
        ans = max(ans, mx - mi);

        mi = INF, mx = -INF;
        for(int i = 0; i < n; ++i)
        {
            tmp = x[i] - y[i];
            mx = max(mx, tmp);
            mi = min(mi, tmp);
        }
        ans = max(ans, mx - mi);

        mi = INF, mx = -INF;
        for(int i = 0; i < n; ++i)
        {
            tmp = -1 * x[i] + y[i];
            mx = max(mx, tmp);
            mi = min(mi, tmp);
        }
        ans = max(ans, mx - mi);

        mi = INF, mx = -INF;
        for(int i = 0; i < n; ++i)
        {
            tmp = -1 * x[i] - y[i];
            mx = max(mx, tmp);
            mi = min(mi, tmp);
        }
        ans = max(ans, mx - mi);
        cout << ans << endl;
    }
    return 0;
}