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

typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
typedef pair<LL, LL> PLL;
typedef pair<int, LL> PIL;
typedef pair<LL, int> PLI;
typedef double DB;

#define pb push_back
#define mset(a, b) memset(a, b, sizeof a)
#define all(x) (x).begin(), (x).end()
#define bit(x) (1 << (x))
#define bitl(x) (1LL << (x))
#define sqr(x) ((x) * (x))
#define sz(x) ((int)(x.size()))
#define counti(x) (__builtin_popcount(x))
#define countl(x) (__builtin_popcountll(x))
#define clz(x) (__builtin_clz(x))
#define clzl(x) (__builtin_clzll(x))
#define ctz(x) (__builtin_ctz(x))
#define ctzl(x) (__builtin_ctzll(x))

#define rep(i, n) for (int (i) = 0; (i) < (int)(n); ++(i))

#define X first
#define Y second

#define Error(x) cout << #x << " = " << x << endl

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

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

const int MN = 1000005;
const LL oo = LL(1e18);
LL n;
LL x[MN], y[MN];
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);
}

int main() {
    
  int tn;
  for (cin >> tn; tn--; ) {
    cin >> n >> seed;
    long long ma1 = -oo, mi1 = oo, ma2 = -oo, mi2 = oo;
    for (int i = 0; i < n; i++) {
      x[i] = rand(-1000000000, 1000000000),
      y[i] = rand(-1000000000, 1000000000);
      chkmin(mi1, x[i] + y[i]);
      chkmax(ma1, x[i] + y[i]);
      chkmin(mi2, x[i] - y[i]);
      chkmax(ma2, x[i] - y[i]);
    }
    printf("%lld\n", max(ma2 - mi2, ma1 - mi1));
  }

  return 0;
}