Truy vấn Josephus

Có $n$ đứa trẻ đứng thành vòng tròn, đánh số từ $1$ đến $n$ theo chiều kim đồng hồ. Chúng chơi trò loại dần: bắt đầu từ đứa số $1$, cứ mỗi đứa thứ hai sẽ bị loại — tức là đứa số $2$ bị loại đầu tiên, rồi đứa số $4$, rồi $6$, và cứ tiếp tục theo vòng tròn cho đến khi tất cả đều bị loại.

Với mỗi truy vấn gồm $n$ và $k$, hãy cho biết đứa trẻ nào bị loại ở vị trí thứ $k$.

Dữ liệu vào

• Dòng đầu: số nguyên $q$ — số truy vấn.
• $q$ dòng tiếp theo, mỗi dòng gồm hai số nguyên $n$ và $k$.

Dữ liệu ra

In $q$ số nguyên, mỗi số trên một dòng — đứa trẻ bị loại ở vị trí thứ $k$ trong vòng tròn $n$ người.

Ràng buộc

• $1\le q\le {10}^5$
• $1\le k\le n\le {10}^9$

Ví dụ