#include <cstdio>
#include <numeric>
#include <iostream>
#include <algorithm>

const double EPS = 1e-7;
const double PI = 3.1415926535897932384626;

const int MAXN = 1100001;

int T, n;
long long seed, x[MAXN], y[MAXN];

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);
}

int main() {
    std::cin >> T;
    for (int cs = 1; cs <= T; cs++) {
        std::cin >> n >> seed;
        for (int i = 0; i < n; i++) {
            x[i] = rand(-1000000000, 1000000000),
            y[i] = rand(-1000000000, 1000000000);
        }
        const long long INF = 1ll << 50;
        long long min1 = INF, max1 = -INF;
        long long min2 = INF, max2 = -INF;
        long long answer = -INF;
        for (int i = 0; i < n; i++) {
            answer = std::max(answer, (x[i] + y[i]) - min1);
            answer = std::max(answer, max2 - (x[i] - y[i]));
            answer = std::max(answer, (x[i] - y[i]) - min2);
            answer = std::max(answer, max1 - (x[i] + y[i]));
            min1 = std::min(min1, x[i] + y[i]);
            min2 = std::min(min2, x[i] - y[i]);
            max1 = std::max(max1, x[i] + y[i]);
            max2 = std::max(max2, x[i] - y[i]);
        }
        std::cout << answer << std::endl;
    }
    return 0;
}