Trong một trò chơi có \(n\) đứa trẻ (đánh số \(1,2,…,n\)) trong một vòng tròn. Trong trò chơi, cứ mỗi hai đứa trẻ thì đứa trẻ sau sẽ bị loại khỏi vòng tròn, cho đến khi không còn đứa trẻ nào.
Nhiệm vụ của bạn là xử lý \(q\) truy vấn có dạng: "Khi có \(n\) đứa trẻ thì đứa trẻ thứ \(k\) sẽ bị loại bỏ là ai?"

Input

• Dòng đầu tiên là \(q\): số lượng truy vấn
• \(q\) dòng tiếp theo, mỗi dòng chứa 2 số \(n\) và \(k\): số đứa trẻ và thứ tự bị loại bỏ của đứa trẻ

Constraints

• \(1 \leq q \leq 10^5\)
• \(1 \leq k \leq n \leq 10^9\)

Output

• \(q\) dòng: đáp án của mỗi truy vấn

Example

4
7 1
7 3
2 2
1337 1313

2
6
1
1107