题目描述

有一个数组 $A_1,\ \ldots,\ A_N$，初始时对于所有 $i$，都有 $A_i = i$。定义操作 $\mathrm{shuffle}(L,\ R)$ 如下：

• 如果 $R = L + 1$，则交换 $A_L$ 和 $A_R$ 的值，然后结束操作。
• 否则，先执行 $\mathrm{shuffle}(L,\ R - 1)$，再执行 $\mathrm{shuffle}(L + 1,\ R)$。

现在要执行一次 $\mathrm{shuffle}(1,\ N)$。请输出操作结束后 $A_K$ 的值。

对于每个输入文件，需要解答 $T$ 个测试用例。

输入格式

输入从标准输入读入，格式如下：

$T$
$case_1$
$case_2$
$\vdots$
$case_T$

每个测试用例格式如下：

$N\ K$

输出格式

输出共 $T$ 行。第 $i$ 行输出第 $i$ 个测试用例的答案。

样例 1

输入

7
2 1
2 2
5 1
5 2
5 3
5 4
5 5

输出

2
1
2
4
1
5
3

说明/提示

数据范围

• $1 \leq T \leq 1000$
• $2 \leq N \leq 10^{18}$
• $1 \leq K \leq N$

样例解释 1

当 $N=2$ 时，执行如下操作得到 $A=(2,1)$。

• 执行 $\mathrm{shuffle}(1,2)$，交换 $A_1$ 和 $A_2$。

当 $N=5$ 时，执行如下操作得到 $A=(2,4,1,5,3)$。

• 执行 $\mathrm{shuffle}(1,5)$。
• 执行 $\mathrm{shuffle}(1,4)$。
• 执行 $\mathrm{shuffle}(1,3)$。
• $\vdots$
• 执行 $\mathrm{shuffle}(2,4)$。
• $\vdots$
• 执行 $\mathrm{shuffle}(2,5)$。
• 执行 $\mathrm{shuffle}(2,4)$。
• $\vdots$
• 执行 $\mathrm{shuffle}(3,5)$。
• $\vdots$

由 ChatGPT 4.1 翻译