Cho một cây nhị phâ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ất của hai đỉnh này.

Dữ liệu

• Dòng đầu tiên chứa số ~T~ ~(1 \le T \le 10^5)~.

• ~T~ dòng tiếp theo, dòng thứ ~i~ chứa hai số ~u_i, v_i~ ~(1 \le u_i, v_i \le 10^{12})~.

Kết quả

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

Ví dụ

Sample Input

3
2 13
14 3
4 11

Sample Output

1
3
2

Giới hạn

• 30% số điểm có ~T \le 10^3; u_i, v_i \le 10^3~

• 30% số điểm có ~T \le 10^5; u_i, v_i \le 10^6~

• 40% số điểm còn lại không có ràng buộc gì thêm.