#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
using namespace std;
#define maxn 1000002
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 n;
long long f[maxn][2];
void input()
{
   cin >> n >> seed;
    for (int i = 0; i < n; i++)
         f[i][0] = rand(-1000000000, 1000000000),
        f[i][1] = rand(-1000000000, 1000000000);
}
void work()
{
    long long a, b;
    long long ans = 0;
    for (int k = 0; k < (1 << 2); k++)
    {
        a = -0x3f3f3f3f;
        b = 0x3f3f3f3f;
        for (int i = 0; i < n; i++)
        {
            long long temp = 0;
            for (int j = 0; j < 2; j++)
                temp += f[i][j] * (((k >> j) & 1) * 2 - 1);
            a = max(a, temp);
            b = min(b, temp);
        }
        ans = max(ans, a - b);
    }
    printf("%I64d\n", ans);
}
int main()
{
    int T=0;
    cin>>T;
    while(T--)
    {
    input();
    work();
   }
    return 0;
}