2018.9 ECNU ICPC/CCPC Trial Round #3

B. 解密信件

单点时限: 1.0 sec

内存限制: 512 MB

oxx 总是喜欢给 ultmaster 写信,由于某些原因,这些信的内容又不能被人看见。但传信的过程中,信中信息的泄露又不可避免,于是 oxx 发明了一种信内容信息的加密方式。ultmaster 拿到了 oxx 的加密程序:

char letter[];

void encrypt(l, r) {
    if (l < r) {
        reverse letter[l..r];
        k = (r - l + 1) / 2;
        encrypt(l, l + k - 1);
        encrypt(l + k, r);
    }
}

其中 reverse letter[l..r] 是将 letter 从 $l$ 到 $r$(闭区间)的子串倒置。

对于某个长度为 $n$,下标从 1 开始的字符串要进行加密,只要调用 encrypt(1, n) 即可。

由于 ultmaster 有超强的理解能力,所以 ultmaster 只需要知道信里面某些位置的信息,就能得知整封信的内容。而 oxx 写了太多的信给 ultmaster 。所以 ultmaster 会有 $T$ 次询问,每一次询问其中一封信的一个位置 $x$,表示加密后的信里的位置,他想知道这个位置在加密前的信里是在什么位置。

众所周知,oxx 有很多话想说,所以信会很长很长。

输入格式

第一行一个整数 $T$ ($1\le T\le 1~000$),表示询问的个数。

接下来的 $T$ 行,每行两个整数 $n$ 和 $x$ ($1\le x\le n\le 10^{18}$),表示信的长度和询问的位置。

输出格式

包含 $T$ 行,每行一个整数,表示对于每一个询问的答案。

样例

Input
4
4 1
4 2
4 3
4 4
Output
3
4
1
2

提示

样例解释:$1234$ $\rightarrow$ $43$|$21$ $\rightarrow$ $3$|$4$|$1$|$2$.