Nội dung bài toán

Xét một trò chơi có n đứa trẻ (được đánh số từ 1, 2, ..., n) đứng thành một vòng tròn. Trong trò chơi này, mỗi lượt sẽ loại bỏ đứa trẻ đứng thứ hai trong thứ tự hiện tại, cho đến khi không còn đứa trẻ nào trong vòng tròn.

Nhiệm vụ của bạn là xử lý q truy vấn. Mỗi truy vấn có dạng: "Khi có n đứa trẻ, đứa trẻ thứ k bị loại là ai?"

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên q – số lượng truy vấn.
• Tiếp theo là q dòng, mỗi dòng chứa hai số nguyên n và k, tương ứng với:
  • n: số lượng đứa trẻ ban đầu.
  • k: vị trí của đứa trẻ bị loại.

Dữ liệu ra

• In ra q số nguyên, mỗi số nguyên là kết quả của một truy vấn, chính là đứa trẻ thứ k bị loại.

Ràng buộc

• ~ 1 \leq q \leq 10^5 ~
• ~ 1 \leq k \leq n \leq 10^9 ~

Ví dụ

Dữ liệu vào

4
7 1
7 3
2 2
1337 1313

Dữ liệu ra

2
6
1
1107

Giải thích ví dụ

1. Truy vấn đầu tiên (n = 7, k = 1):

   • Có 7 đứa trẻ, lần lượt bị loại bỏ theo thứ tự: 2, 4, 6, 1, 5, 3, 7.
   • Đứa trẻ bị loại đầu tiên (k = 1) là 2.

2. Truy vấn thứ hai (n = 7, k = 3):

   • Với cùng n = 7, lần lượt loại bỏ như trên: 2, 4, 6, 1, 5, 3, 7.
   • Đứa trẻ thứ ba bị loại (k = 3) là 6.

3. Truy vấn thứ ba (n = 2, k = 2):

   • Có 2 đứa trẻ, lần lượt bị loại: 2, 1.
   • Đứa trẻ thứ hai bị loại (k = 2) là 1.

4. Truy vấn thứ tư (n = 1337, k = 1313):

   • Với số lượng lớn đứa trẻ ~ n = 1337 ~, không thể duyệt toàn bộ. Sử dụng quy luật toán học để tính được kết quả là 1107.