配点 : $500$ 点

問題文

配列 $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$ 個解いてください。

制約

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

入力

入力は、標準入力から以下の形式で与えられる。

$T$

$case_1$

$case_2$

$\vdots$

$case_T$

各ケースは、以下の形式である。

$N$ $K$

出力

$T$ 行出力せよ。$i$ 行目に、$i$ 個目のテストケースの答えを出力すること。

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

2
1
2
4
1
5
3

$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$
• $\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$