#include <iostream>
using namespace std;
int T, 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);
}
const int maxn = 1000009;
const int INF = 1000000007;
long long x[maxn], y[maxn];
int main() {
    int ans = 0;
    cin >> T;
    while (T--) {
        cin >> n >> seed;
        ans = 0;
        for (int i = 0; i < n; i++)
        x[i] = rand(-1000000000, 1000000000),
        y[i] = rand(-1000000000, 1000000000);
        for (int s = 0; s < 4; ++s) {
            int mi = INF,ma = -INF;
            for (int i = 0; i < n; ++i) {
                int t = 0;
                if (s & 1) t += y[i];
                else t -= y[i];
                if (s & 2) t += x[i];
                else t -= x[i];
                mi = min(mi, t);
                ma = max(ma, t);
            }
            ans = max(ans, ma - mi);
        }
        cout << ans << endl;
    }
    return 0;
}