Truy vấn thứ tự loại vòng tròn

Bối cảnh và bài toán

Có n vị trí 1..n trên vòng tròn. Ở mỗi lượt quét, cứ bỏ một vị trí còn sống rồi giữ một vị trí theo quy tắc loại mọi vị trí thứ hai như bài Josephus chuẩn. Với mỗi truy vấn (n,k), cần biết vị trí bị loại thứ k, trong khi n có thể tới 10^9.

Yêu cầu

Trả lời vị trí bị loại thứ k cho từng truy vấn.

Input

• Dòng 1: số truy vấn q.
• Mỗi dòng tiếp: n k.

Output

Mỗi truy vấn in một đáp án.

Ràng buộc

• 1 <= q <= 10^5
• 1 <= k <= n <= 10^9

Chấm điểm

Ví dụ 1

Input

4
7 1
7 3
2 2
1337 1313

Output

2
6
1
1107

Giải thích. Kết quả theo thứ tự loại every-second của từng kích thước vòng.

Ví dụ 2

Input

3
10 1
10 5
10 6

Output

2
10
3

Giải thích. Năm người đầu tiên bị loại là các số chẵn 2,4,6,8,10; sau đó bài toán thu nhỏ trên các số lẻ.

Thông tin bài tập

Nguồn: Phỏng theo CSES Problem Set — Josephus Queries (Task 2164).

Tham khảo: https://cses.fi/problemset/task/2164/