Trò chơi Josephus được thể hiện như sau:

• \(n\) người (được đánh số từ \(1\) đến \(n\)) được xếp lần lượt trên vòng tròn.
• Trong quá trình trò chơi diễn ra, "người thứ hai" sẽ lần lượt bị đưa ra khỏi vòng tròn cho đến khi chỉ còn một người.

\(q\) câu hỏi: Bạn được cho trước số nguyên dương \(n\), tìm số thứ tự của người cuối cùng.

Minh họa

• \(n=5\)

• \(n=6\)

• \(n=7\)

• \(n=13\)

Input

• Dòng đầu chứa 2 số nguyên dương \(q\) - là số câu hỏi.
• \(q\) dòng tiếp theo mỗi dòng chứa hai số nguyên dương \(n\).

Output

• \(q\) dòng, mỗi dòng chứa số thứ tự của người cuối cùng.

Constants

• \(1 \leq q \leq 10\) và \(1 \leq n \leq 10^9\)

Example

4
5
6
7
13

3
5
7
11