RR có ~1~ cục gạch và cần biết cục gạch này nặng chính xác bao nhiêu kg. RR biết được cái cục gạch này nặng trong khoảng [~L~, ~R~].

RR có ~1~ cái cân kỳ diệu:

• Gồm ~2~ đĩa cân
• Mỗi lần cân biết được bên nào nặng hơn / nhẹ hơn / bằng nhau.
• Có các quả cân: ~1~, ~3~, ~9~, ~27~, ..., ~3^{i}~. Không có ~2~ quả cân bằng nhau.
• Có thể đặt quả cân lên cả ~2~ bên.

Vì là cân kỳ diệu, nên mỗi lần dùng cân sẽ mất số tiền là số lượng quả cân đặt lên cân. Bạn cần tính xem để xác định chính xác cân nặng của cục gạch cần mất bao tiền.

Chú ý: Mỗi lần cân là cân ~1~ phát, ~1~ bên có cục gạch + ~1~ số quả cân, ~1~ bên có ~1~ số quả cân khác. Không chơi bẩn kiểu như:

• Đặt quả cân ~x~ lên, xem nặng hơn hay nhẹ hơn, rồi lại đặt thêm quả cân ~y~ xem nặng hơn hay nhẹ hơn. Nếu làm như thế tính là ~2~ lần cân.
• Không chơi bẩn theo kiểu lượt trước đang có mấy quả cân trên đĩa rồi lượt sau đặt thêm cục gạch lên rồi lại bỏ bớt quả cân xuống xem bên nào nặng hơn. Như thế cũng tính là ~2~ lần cân.
• Bẻ cục gạch ra làm ~2~ phần rồi tính toán các kiểu.

Input

Dòng ~1~: ~Q~ - số truy vấn

~Q~ dòng tiếp, mỗi dòng ~2~ số ~L~ và ~R~.

Output

Gồm Q số là kết quả cho Q truy vấn.

Giới hạn

• ~1 \le L \le R \le 10\,000~.
• ~Q \le 10^{6}~.

Sample Input

3
1 3
3 13
15 20

Sample Output

2
5
6