Cho một cây lớn vô hạn, có gốc là đỉnh \(1\). Mọi đỉnh \(i\) ở trên cây đều có hai đỉnh con trực tiếp là \(2 \cdot i\) và \(2 \cdot i + 1\).

Bạn được hỏi \(T\) câu hỏi, câu hỏi thứ \(i\) sẽ gồm hai đỉnh \(u_i, v_i\). Bạn cần tìm tổ tiên chung gần nhất của hai đỉnh này.

Input

• Dòng đầu tiên chứa số \(T\) (\(1 \leq T \leq 10^5\)).
• \(T\) dòng tiếp theo, dòng thứ \(i\) chứa hai số \(u_i, v_i\) (\(1 \leq u_i, v_i \leq 10^{12}\)).

Output

• In ra \(T\) dòng, dòng thứ \(i\) là đáp án của câu hỏi thứ \(i\).

Scoring

• Subtask 1 (\(30\%\) số điểm): \(T \le 10^3\), \(u_i, v_i \le 10^3\).
• Subtask 2 (\(30\%\) số điểm): \(T \le 10^5\), \(u_i, v_i \le 10^6\).
• Subtask 3 (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Example

3
2 13
14 3
4 11

1
3
2