#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <utility>
#include <vector>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int((x).size()))
#define bit(x) (1 << (x))
#define cnt1(x) (__builtin_popcount(x))

template<class T, class U>
inline void chkmax(T& x, U y) {
    if (x < y) x = y;
}

template<class T, class U>
inline void chkmin(T& x, U y) {
    if (y < x) x = y;
}

typedef long long LL;
typedef double DB;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int INF = 1000000000;
const LL INFL = 1LL << 60;
LL sed;

inline LL rand(LL le, LL ri) {
    static LL mo = 1e9 + 7, g = 78125;
    return le + ((sed *= g) %= mo) % (ri - le + 1);
}

int main() {
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    
    int tc, n;
    LL x, y, xx, yy, sx, sy, ex, ey;
    
    for (scanf("%d", &tc); tc--; ) {
        scanf("%d%lld", &n, &sed);
        sx = sy = INFL, ex = ey = -INFL;
        while (n--) {
            x = rand(-INF, INF);
            y = rand(-INF, INF);
            xx = x + y, yy = x - y;
            chkmin(sx, xx), chkmax(ex, xx);
            chkmin(sy, yy), chkmax(ey, yy);
        }
        printf("%lld\n", max(ex - sx, ey - sy));
    }
    return 0;
}