#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

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 t;
    scanf("%d", &t);
    while(t--)
    {
        int n;
        scanf("%d%lld", &n, &seed);
        long long a = -1e10, aa = 1e10, b = -1e10, bb = 1e10, 
            c = -1e10, cc = 1e10, d = -1e10, dd = 1e10;
        for (int i = 0 ; i < n ; i++)
        {
            long long x = rand(-1000000000, 1000000000);
            long long y = rand(-1000000000, 1000000000); 
            a = max(a, x + y);
            aa = min(a, x + y);
            b = max(b, x - y);
            bb = min(bb, x - y);
            c = max(c, y - x);
            cc = min(cc, y - x);
            d = max(d, -x - y);
            dd = min(dd, -x - y);
        }
        
        long long ans = 0;
        ans = max(ans, a - aa);
        ans = max(ans, b - bb);
        ans = max(ans, c - cc);
        ans = max(ans, d - dd);
        printf("%lld\n", ans);
    } 
    return 0;
}