Nhà của Bờm có nuôi một bầy heo. Hiện có một con heo đã nuổi đủ ngày tuổi và cần xẻ thịt đem bán. Trước tiên Bờm cần phải biết được cân nặng chính xác của nó. Nhưng cái cân ở nhà đã hỏng mất ròi, nên chỉ biết được nó nặng không nhỏ hơn \(L\) (Kg) và không lớn hơn \(R\) (Kg). Vậy là Bờm phải chạy sang mượn cân của nhà Phú Ông kế bên.

Bộ cân nhà Phú Ông rất đặc biệt, bao gồm :

• Một cân đĩa thăng bằng: Cân sẽ cho biết mối quan hệ của hai khối lượng trong một lần cân - bé hơn, lớn hơn hoặc bằng nhau.
• Một dãy vô tận các quả cân có dạng \(1\), \(3\), \(9\), \(27\),..., \(3^i\), ... theo Kilogram. Nhưng mỗi dạng chỉ có đúng một quả.
• Phú Ông muốn lợi dụng cơ hội này để kiếm ít tiền từ Bờm, nên đặt ra điều kiện: "Với mỗi quả cân Bờm đặt lên cân một lần phải tốn \(1\) đồng. Chi phí một lần cân sẽ bằng số quả cân sử dụng trong lần đó. Và chi phí để xác định được trọng lượng của một con heo chính là tổng chi phí các lần cân".

Bờm nhà ta rất thông minh, sau một hồi suy nghĩ, Bờm bảo với Phú Ông rằng: "Bờm chắc chắn \(100\%\) rằng Phú Ông sẽ chỉ lấy được tối đa là \(E\) đồng mà thôi".

Bạn hãy cho biết số \(E\) đó nhỏ nhất có thể là bao nhiêu? Biết rằng:

• Con heo nhà Bờm có cân nặng là một số nguyên dương theo Kilogram;
• Bờm sẽ không xẻ nhỏ con heo đến khi xác định được cân nặng chính xác của nó;
• Có thể đặt các quả cân tùy ý lên hai đĩa cân;
• Trong một lần cân, phải đặt các quả cân trước khi đặt heo lên;
• Sau một lần cân bắt buộc phải lấy xuống tất cả những quả cân đang ở trên các đĩa (nên khi bắt đầu một lần cân mới, hai đĩa cân đều không chứa vật);

Input

• Dòng đầu tiên là số nguyên dương \(Q (Q \leq 1000000)\) cho biết số trường hợp bạn cần phải tính toán;
• \(Q\) dòng tiếp theo, mỗi dòng là một cặp số nguyên dương \(L\) và \(R\) \((1 \leq L \leq R \leq 10000)\) cho biết giới hạn cân nặng con heo của Bờm.

Output

• Gồm \(Q\) dòng là số \(E\) tương ứng với mỗi trường hợp.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(R \leq 500\);
• Subtask \(2\) (\(20\%\) số điểm): \(R \leq 5000\);
• Subtask \(3\) (\(60\%\) số điểm): \(R \leq 10000\);

Example

3
1 3
3 13
15 20

2
5
6