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à 2i và 2i + 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ấtcủa hai đỉnh này.

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})

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

• 30% số điểm có T ≤ 10^3; u_i, v_i \leq 10^3
• 30% số điểm có T ≤ 10^5; u_i, v_i \leq 10^6
• 40% số điểm có điều kiện gốc.