//
//  main.cpp
//  bc72.div1.1001-Clarke and points
//
//  Created by eycia on 16/2/13.
//  Copyright © 2016年 eycia. All rights reserved.
//

#include <iostream>
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 argc, const char * argv[]) {
    long long n, t;
    
    cin >> t;
    while (t--) {
    
    long long ma1 = -2100000000;
    long long ma2 = -2100000000;
    long long mi1 = 2100000000;
    long long mi2 = 2100000000;
    
    cin >> n >> seed;
    for (int i = 0; i < n; i++) {
        long long xx = rand(-1000000000, 1000000000);
        long long yy = rand(-1000000000, 1000000000);
        
        ma1 = max(ma1, xx+yy);
        ma2 = max(ma2, xx-yy);
        
        mi1 = min(mi1, xx+yy);
        mi2 = min(mi2, xx-yy);
    }
    
    cout << max(ma1-mi1, ma2-mi2) << endl;
    }
}