/*
ye mera template hai
apna khud likho bc :P
*/
/*
Author : Sarvagya Agarwal
*/
#include<bits/stdc++.h>
using namespace std;
//defines
#define openin freopen("input.txt","r",stdin)
#define openout freopen("output.txt","w",stdout)
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ll long long
#define mod 1000000007
#define repr(i,x,y) for (__typeof(x) i=x;i>=y;i--)
#define rep(i,x,y) for (__typeof(x) i=x;i<=y;i++)
#define all(c) (c).begin(),(c).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
/* Print pair */
template <typename T,typename S>
ostream & operator << (ostream &os , const pair<T,S> &v) {
os << "(" ;
os << v.first << "," << v.second << ")" ;
return os ;
}
/* Print vector */
template <typename T>
ostream & operator << (ostream &os , const vector<T> &v) {
os << "[" ;
int sz = v.size() ;
for(int i = 0 ; i < sz ; ++i) {
os << v[i] ;
if(i!=sz-1)os << "," ;
}
os << "]\n" ;
return os ;
}
/* Print set */
template <typename T>
ostream & operator << (ostream &os , const set<T> &v) {
T last = *v.rbegin() ;
os << "[" ;
for(auto it : v) {
os << it ;
if(it != last) os << "," ;
}
os << "]\n" ;
return os ;
}
/* Print Map */
template <typename T,typename S>
ostream & operator << (ostream &os , const map<T,S> &v) {
for(auto it : v) {
os << it.first << " : " << it.second << "\n" ;
}
return os ;
}
int power(int a , int b)
{
int res = 1 ;
while(b)
{
if(b%2) {
res = (res * a) % mod ;
}
b/=2 ;
a = (a*a) % mod ;
}
return res ;
}
//debug
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
bool is_power_of_two(int n)
{
if(n == 0) return false ;
return (n & (n-1)) == 0 ;
}
int count_bits(int n)
{
return __builtin_popcount(n) ;
}
int count_bits_ll(int n)
{
return __builtin_popcountll(n) ;
}
int largest_power(int n)
{
int i ;
for(i = 1 ; i <= n ; i *= 2) ;
return i/2 ;
}
const int N = 1e6 + 5 ;
int n , arr[N * 4] , rem ;
void update(int i,int l,int r,int idx,int val)
{
if(l == r) {
arr[i] = val ;
return ;
}
int m = (l + r) / 2 ;
if(idx <= m) update(i*2,l,m,idx,val) ;
else update(i*2+1,m+1,r,idx,val) ;
arr[i] = arr[i*2] + arr[i*2+1] ;
}
void build(int i,int l,int r)
{
if(l == r) {
arr[i] = 1 ;
return ;
}
int m = l + r >> 1 ;
build(i * 2 , l , m ) ;
build(i * 2 + 1 , m + 1 , r) ;
arr[i] = arr[i*2] + arr[i*2+1] ;
}
int query_cnt(int i,int l,int r,int s,int e)
{
if(l > r || r < s || l > e) return 0 ;
if(l >= s and r <= e) return arr[i] ;
int m = l + r >> 1 ;
return query_cnt(i*2,l,m,s,e) + query_cnt(i*2+1,m+1,r,s,e) ;
}
int query(int i,int l,int r,int k)
{
//trace(i,l,r,k,arr[i]);
if(l==r) return l ;
int m = (l + r) >> 1 ;
int L = arr[i * 2] ;
int R = arr[i*2+1] ;
if(k <= L) return query(i*2,l,m,k) ;
else return query(i*2+1,m+1,r,k-L) ;
}
int get_c(int index , int k)
{
if(k > rem)k %= rem ;
if(k == 0) k = rem ;
// return kth remaining from index 'index'
int cnt = query_cnt(1,1,n,index,n) ;
int cnt2 = query_cnt(1,1,n,1,index-1) ;
if(k <= cnt) {
return query(1,1,n,cnt2 + k) ;
}
else {
return query(1,1,n,k-cnt) ;
}
}
int get_ac(int index , int k)
{
if(k > rem)k %= rem ;
if(k == 0) k = rem ;
// return kth remaining from index 'index'
int cnt = query_cnt(1,1,n,index+1,n) ;
int cnt2 = query_cnt(1,1,n,1,index) ;
if(k <= cnt2) {
return query(1,1,n,cnt2+1-k) ;
}
else {
return query(1,1,n,cnt-k+1+cnt2+cnt2) ;
}
}
int main()
{
int t ;
scanf("%d",&t) ;
//cin >> t ;
while(t--) {
scanf("%d",&n) ;ll k ; scanf("%lld",&k) ;
build(1,1,n) ;
rem = n ;
if(k > 0) {
int index = 1 ;
ll kk = k ;
bool clock = true ;
rep(i,1,n-1) {
int temp ;
if(clock) {
temp = get_c(index , kk) ;
}
else {
temp = get_ac(index , kk) ;
}
update(1,1,n,temp,0) ;
index = temp ;
clock ^= true ;
kk += k ; rem-- ;
}
printf("%d\n",query(1,1,n,1));// << "\n" ;
}
else {
int index = 1 ;
ll kk = k ;
bool clock = false ;
rep(i,1,n-1) {
int temp ;
if(clock) {
temp = get_c(index , -kk) ;
}
else {
temp = get_ac(index , -kk) ;
}
update(1,1,n,temp,0) ;
index = temp ;
clock ^= true ;
kk += k ;rem--;
}
printf("%d\n",query(1,1,n,1));
}
}
return 0;
}
LyoKeWUgbWVyYSB0ZW1wbGF0ZSBoYWkKYXBuYSBraHVkIGxpa2hvIGJjIDpQCiovCgovKgpBdXRob3IgOiBTYXJ2YWd5YSBBZ2Fyd2FsCiovCgojaW5jbHVkZTxiaXRzL3N0ZGMrKy5oPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKLy9kZWZpbmVzCiNkZWZpbmUgb3BlbmluIGZyZW9wZW4oImlucHV0LnR4dCIsInIiLHN0ZGluKQojZGVmaW5lIG9wZW5vdXQgZnJlb3Blbigib3V0cHV0LnR4dCIsInciLHN0ZG91dCkKI2RlZmluZSBmYXN0IGlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpO2Npbi50aWUoMCk7Y291dC50aWUoMCkKI2RlZmluZSBsbCBsb25nIGxvbmcKI2RlZmluZSBtb2QgMTAwMDAwMDAwNwojZGVmaW5lIHJlcHIoaSx4LHkpIGZvciAoX190eXBlb2YoeCkgaT14O2k+PXk7aS0tKQojZGVmaW5lIHJlcChpLHgseSkgZm9yIChfX3R5cGVvZih4KSBpPXg7aTw9eTtpKyspCiNkZWZpbmUgYWxsKGMpIChjKS5iZWdpbigpLChjKS5lbmQoKQojZGVmaW5lIGZmIGZpcnN0CiNkZWZpbmUgc3Mgc2Vjb25kCiNkZWZpbmUgcGIgcHVzaF9iYWNrCiNkZWZpbmUgbXAgbWFrZV9wYWlyCgovKiBQcmludCBwYWlyICovCnRlbXBsYXRlIDx0eXBlbmFtZSBULHR5cGVuYW1lIFM+Cm9zdHJlYW0gJiBvcGVyYXRvciA8PCAob3N0cmVhbSAmb3MgLCBjb25zdCBwYWlyPFQsUz4gJnYpIHsKICAgIG9zIDw8ICIoIiA7CiAgICBvcyA8PCB2LmZpcnN0IDw8ICIsIiA8PCB2LnNlY29uZCA8PCAiKSIgOwogICAgcmV0dXJuIG9zIDsKfQovKiBQcmludCB2ZWN0b3IgKi8KdGVtcGxhdGUgPHR5cGVuYW1lIFQ+Cm9zdHJlYW0gJiBvcGVyYXRvciA8PCAob3N0cmVhbSAmb3MgLCBjb25zdCB2ZWN0b3I8VD4gJnYpIHsKICAgIG9zIDw8ICJbIiA7CiAgICBpbnQgc3ogPSB2LnNpemUoKSA7CiAgICBmb3IoaW50IGkgPSAwIDsgaSA8IHN6IDsgKytpKSB7CiAgICAgICAgb3MgPDwgdltpXSA7CiAgICAgICAgaWYoaSE9c3otMSlvcyA8PCAiLCIgOwogICAgfQogICAgb3MgPDwgIl1cbiIgOwogICAgcmV0dXJuIG9zIDsKfQovKiBQcmludCBzZXQgKi8KdGVtcGxhdGUgPHR5cGVuYW1lIFQ+Cm9zdHJlYW0gJiBvcGVyYXRvciA8PCAob3N0cmVhbSAmb3MgLCBjb25zdCBzZXQ8VD4gJnYpIHsKICAgIFQgbGFzdCA9ICp2LnJiZWdpbigpIDsKICAgIG9zIDw8ICJbIiA7CiAgICBmb3IoYXV0byBpdCA6IHYpIHsKICAgICAgICBvcyA8PCBpdCAgOwogICAgICAgIGlmKGl0ICE9IGxhc3QpIG9zIDw8ICIsIiA7CiAgICB9CiAgICBvcyA8PCAiXVxuIiA7CiAgICByZXR1cm4gb3MgOwp9Ci8qIFByaW50IE1hcCAqLwp0ZW1wbGF0ZSA8dHlwZW5hbWUgVCx0eXBlbmFtZSBTPgpvc3RyZWFtICYgb3BlcmF0b3IgPDwgKG9zdHJlYW0gJm9zICwgY29uc3QgbWFwPFQsUz4gJnYpIHsKICAgIGZvcihhdXRvIGl0IDogdikgewogICAgICAgIG9zIDw8IGl0LmZpcnN0IDw8ICIgOiAiIDw8IGl0LnNlY29uZCA8PCAiXG4iIDsKICAgIH0KICAgIHJldHVybiBvcyA7Cn0KaW50IHBvd2VyKGludCBhICwgaW50IGIpCnsKICAgIGludCByZXMgPSAxIDsKICAgIHdoaWxlKGIpCiAgICB7CiAgICAgICAgaWYoYiUyKSB7CiAgICAgICAgICAgIHJlcyA9IChyZXMgKiBhKSAlIG1vZCA7CiAgICAgICAgfQogICAgICAgIGIvPTIgOwogICAgICAgIGEgPSAoYSphKSAlIG1vZCA7CiAgICB9CiAgICByZXR1cm4gcmVzIDsKfQoKLy9kZWJ1ZwojZGVmaW5lIFRSQUNFCgojaWZkZWYgVFJBQ0UKI2RlZmluZSB0cmFjZSguLi4pIF9fZigjX19WQV9BUkdTX18sIF9fVkFfQVJHU19fKQp0ZW1wbGF0ZSA8dHlwZW5hbWUgQXJnMT4Kdm9pZCBfX2YoY29uc3QgY2hhciogbmFtZSwgQXJnMSYmIGFyZzEpewoJCWNlcnIgPDwgbmFtZSA8PCAiIDogIiA8PCBhcmcxIDw8IHN0ZDo6ZW5kbDsKfQp0ZW1wbGF0ZSA8dHlwZW5hbWUgQXJnMSwgdHlwZW5hbWUuLi4gQXJncz4Kdm9pZCBfX2YoY29uc3QgY2hhciogbmFtZXMsIEFyZzEmJiBhcmcxLCBBcmdzJiYuLi4gYXJncyl7CgkJY29uc3QgY2hhciogY29tbWEgPSBzdHJjaHIobmFtZXMgKyAxLCAnLCcpO2NlcnIud3JpdGUobmFtZXMsIGNvbW1hIC0gbmFtZXMpIDw8ICIgOiAiIDw8IGFyZzE8PCIgfCAiO19fZihjb21tYSsxLCBhcmdzLi4uKTsKfQojZWxzZQojZGVmaW5lIHRyYWNlKC4uLikKI2VuZGlmCmJvb2wgaXNfcG93ZXJfb2ZfdHdvKGludCBuKQp7CiAgICBpZihuID09IDApIHJldHVybiBmYWxzZSA7CiAgICByZXR1cm4gKG4gJiAobi0xKSkgPT0gMCA7Cn0KaW50IGNvdW50X2JpdHMoaW50IG4pCnsKICAgIHJldHVybiBfX2J1aWx0aW5fcG9wY291bnQobikgOwp9CmludCBjb3VudF9iaXRzX2xsKGludCBuKQp7CiAgICByZXR1cm4gX19idWlsdGluX3BvcGNvdW50bGwobikgOwp9CmludCBsYXJnZXN0X3Bvd2VyKGludCBuKQp7CiAgICBpbnQgaSA7CiAgICBmb3IoaSA9IDEgOyBpIDw9IG4gOyBpICo9IDIpIDsKICAgIHJldHVybiBpLzIgOwp9CmNvbnN0IGludCBOID0gMWU2ICsgNSA7CmludCBuICwgYXJyW04gKiA0XSAsIHJlbSA7CnZvaWQgdXBkYXRlKGludCBpLGludCBsLGludCByLGludCBpZHgsaW50IHZhbCkKewogICAgaWYobCA9PSByKSB7CiAgICAgICAgYXJyW2ldID0gdmFsIDsKICAgICAgICByZXR1cm4gOwogICAgfQogICAgaW50IG0gPSAobCArIHIpIC8gMiA7CiAgICBpZihpZHggPD0gbSkgdXBkYXRlKGkqMixsLG0saWR4LHZhbCkgOwogICAgZWxzZSB1cGRhdGUoaSoyKzEsbSsxLHIsaWR4LHZhbCkgOwogICAgYXJyW2ldID0gYXJyW2kqMl0gKyBhcnJbaSoyKzFdIDsKfQp2b2lkIGJ1aWxkKGludCBpLGludCBsLGludCByKQp7CiAgICBpZihsID09IHIpIHsKICAgICAgICBhcnJbaV0gPSAxIDsKICAgICAgICByZXR1cm4gOwogICAgfQogICAgaW50IG0gPSBsICsgciA+PiAxIDsKICAgIGJ1aWxkKGkgKiAyICwgbCAsIG0gKSA7CiAgICBidWlsZChpICogMiArIDEgLCBtICsgMSAsIHIpIDsKICAgIGFycltpXSA9IGFycltpKjJdICsgYXJyW2kqMisxXSA7Cn0KaW50IHF1ZXJ5X2NudChpbnQgaSxpbnQgbCxpbnQgcixpbnQgcyxpbnQgZSkKewogICAgaWYobCA+IHIgfHwgciA8IHMgfHwgbCA+IGUpIHJldHVybiAwIDsKICAgIGlmKGwgPj0gcyBhbmQgciA8PSBlKSByZXR1cm4gYXJyW2ldIDsKICAgIGludCBtID0gbCArIHIgPj4gMSA7CiAgICByZXR1cm4gcXVlcnlfY250KGkqMixsLG0scyxlKSArIHF1ZXJ5X2NudChpKjIrMSxtKzEscixzLGUpIDsKfQppbnQgcXVlcnkoaW50IGksaW50IGwsaW50IHIsaW50IGspCnsKICAgIC8vdHJhY2UoaSxsLHIsayxhcnJbaV0pOwogICAgaWYobD09cikgcmV0dXJuIGwgOwogICAgaW50IG0gPSAobCArIHIpID4+IDEgOwogICAgaW50IEwgPSBhcnJbaSAqIDJdIDsKICAgIGludCBSID0gYXJyW2kqMisxXSA7CiAgICBpZihrIDw9IEwpIHJldHVybiBxdWVyeShpKjIsbCxtLGspIDsKICAgIGVsc2UgcmV0dXJuIHF1ZXJ5KGkqMisxLG0rMSxyLGstTCkgOwp9CmludCBnZXRfYyhpbnQgaW5kZXggLCBpbnQgaykKewogICAgaWYoayA+IHJlbSlrICU9IHJlbSA7CiAgICBpZihrID09IDApIGsgPSByZW0gOwogICAgLy8gcmV0dXJuIGt0aCByZW1haW5pbmcgZnJvbSBpbmRleCAnaW5kZXgnCiAgICBpbnQgY250ID0gcXVlcnlfY250KDEsMSxuLGluZGV4LG4pIDsKICAgIGludCBjbnQyID0gcXVlcnlfY250KDEsMSxuLDEsaW5kZXgtMSkgOwogICAgaWYoayA8PSBjbnQpIHsKICAgICAgICByZXR1cm4gcXVlcnkoMSwxLG4sY250MiArIGspIDsKICAgIH0KICAgIGVsc2UgewogICAgICAgIHJldHVybiBxdWVyeSgxLDEsbixrLWNudCkgOwogICAgfQp9CmludCBnZXRfYWMoaW50IGluZGV4ICwgaW50IGspCnsKCiAgICBpZihrID4gcmVtKWsgJT0gcmVtIDsKICAgIGlmKGsgPT0gMCkgayA9IHJlbSA7CiAgICAvLyByZXR1cm4ga3RoIHJlbWFpbmluZyBmcm9tIGluZGV4ICdpbmRleCcKICAgIGludCBjbnQgPSBxdWVyeV9jbnQoMSwxLG4saW5kZXgrMSxuKSA7CiAgICBpbnQgY250MiA9IHF1ZXJ5X2NudCgxLDEsbiwxLGluZGV4KSA7CiAgICBpZihrIDw9IGNudDIpIHsKICAgICAgICByZXR1cm4gcXVlcnkoMSwxLG4sY250MisxLWspIDsKICAgIH0KICAgIGVsc2UgewogICAgICAgIHJldHVybiBxdWVyeSgxLDEsbixjbnQtaysxK2NudDIrY250MikgOwogICAgfQp9CmludCBtYWluKCkKewogICAgaW50IHQgOwogICAgc2NhbmYoIiVkIiwmdCkgOwogICAgLy9jaW4gPj4gdCA7CiAgICB3aGlsZSh0LS0pIHsKICAgICAgICBzY2FuZigiJWQiLCZuKSA7bGwgayA7IHNjYW5mKCIlbGxkIiwmaykgOwogICAgICAgIGJ1aWxkKDEsMSxuKSA7CiAgICAgICAgcmVtID0gbiA7CiAgICAgICAgaWYoayA+IDApIHsKICAgICAgICAgICAgaW50IGluZGV4ID0gMSA7CiAgICAgICAgICAgIGxsIGtrID0gayA7IAogICAgICAgICAgICBib29sIGNsb2NrID0gdHJ1ZSA7CiAgICAgICAgICAgIHJlcChpLDEsbi0xKSB7CiAgICAgICAgICAgICAgICBpbnQgdGVtcCA7CiAgICAgICAgICAgICAgICBpZihjbG9jaykgewogICAgICAgICAgICAgICAgICAgIHRlbXAgPSBnZXRfYyhpbmRleCAsIGtrKSA7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBlbHNlIHsKICAgICAgICAgICAgICAgICAgICB0ZW1wID0gZ2V0X2FjKGluZGV4ICwga2spIDsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIHVwZGF0ZSgxLDEsbix0ZW1wLDApIDsKICAgICAgICAgICAgICAgIGluZGV4ID0gdGVtcCA7CiAgICAgICAgICAgICAgICBjbG9jayBePSB0cnVlIDsKICAgICAgICAgICAgICAgIGtrICs9IGsgOyByZW0tLSA7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgcHJpbnRmKCIlZFxuIixxdWVyeSgxLDEsbiwxKSk7Ly8gPDwgIlxuIiA7CiAgICAgICAgfQogICAgICAgIGVsc2UgewogICAgICAgICAgICBpbnQgaW5kZXggPSAxIDsKICAgICAgICAgICAgbGwga2sgPSBrIDsgCiAgICAgICAgICAgIGJvb2wgY2xvY2sgPSBmYWxzZSA7CiAgICAgICAgICAgIHJlcChpLDEsbi0xKSB7CiAgICAgICAgICAgICAgICBpbnQgdGVtcCA7CiAgICAgICAgICAgICAgICBpZihjbG9jaykgewogICAgICAgICAgICAgICAgICAgIHRlbXAgPSBnZXRfYyhpbmRleCAsIC1raykgOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgZWxzZSB7CiAgICAgICAgICAgICAgICAgICAgdGVtcCA9IGdldF9hYyhpbmRleCAsIC1raykgOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgdXBkYXRlKDEsMSxuLHRlbXAsMCkgOwogICAgICAgICAgICAgICAgaW5kZXggPSB0ZW1wIDsKICAgICAgICAgICAgICAgIGNsb2NrIF49IHRydWUgOwogICAgICAgICAgICAgICAga2sgKz0gayA7cmVtLS07CiAgICAgICAgICAgIH0KICAgICAgICAgICAgcHJpbnRmKCIlZFxuIixxdWVyeSgxLDEsbiwxKSk7CiAgICAgICAgfQogICAgfQogICAgcmV0dXJuIDA7Cn0K