A - Long Shuffle Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 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 個目のテストケースの答えを出力すること。

入力例 1

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

出力例 1

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

Score : 500 points

Problem Statement

There is an array A_1, \ldots, A_N, and initially A_i = i for all i. Define the following routine \mathrm{shuffle}(L, R):

  • If R = L + 1, swap values of A_L and A_R and terminate.
  • Otherwise, run \mathrm{shuffle}(L, R - 1) followed by \mathrm{shuffle}(L + 1, R).

Suppose we run \mathrm{shuffle}(1, N). Print the value of A_K after the routine finishes.

For each input file, solve T test cases.

Constraints

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

Input

The input is given from Standard Input in the following format:

T
case_1
case_2
\vdots
case_T

Each case is in the following format:

N K

Output

Print T lines. The i-th line should contain the answer for the i-th case.

Sample Input 1

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

Sample Output 1

2
1
2
4
1
5
3

For N=2, we do the following and get A=(2,1).

  • Run \mathrm{shuffle}(1, 2), and swap A_1 and A_2.

For N=5, we do the following and get A=(2,4,1,5,3).

  • Run \mathrm{shuffle}(1, 5):
    • Run \mathrm{shuffle}(1, 4):
      • Run \mathrm{shuffle}(1, 3):
        • \vdots
      • Run \mathrm{shuffle}(2, 4):
        • \vdots
    • Run \mathrm{shuffle}(2, 5):
      • Run \mathrm{shuffle}(2, 4):
        • \vdots
      • Run \mathrm{shuffle}(3, 5):
        • \vdots