Giải bài trực tuyến

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 2 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ⁱ, ... 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 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 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.

Giới hạn

• Q ≤ 1000000;
• 1 ≤ L ≤ R ≤ 10000;
• 20% số test có R ≤ 500;
• 40% số test có R ≤ 5000;

Chấm điểm

Bài của bạn sẽ được chấm trên thang điểm 100. Điểm mà bạn nhận được sẽ tương ứng với % test mà bạn giải đúng.

Trong quá trình thi, bài của bạn sẽ chỉ được chấm với 1 test ví dụ có trong đề bài.

Khi vòng thi kết thúc, bài của bạn sẽ được chấm với bộ test đầy đủ.

Example

Input:
3
1 3
3 13
15 20

Output:
2
5
6

Giải thích

Trong trường hợp đầu tiên, con heo nhà Bờm nặng trong khoản [1;3] (Kg). Có nhiều cách để Bờm chỉ tốn tối đa 2 đồng. Và đây là một trong những cách đó:

• Đặt lên đĩa bên TRÁI: quả cân 1 (Kg);
• Đặt lên đĩa bên PHẢI: quả cân 3 (Kg);
• Cuối cùng đặt heo lên đĩa bên TRÁI;

Nếu:

• Trái > Phải : heo nặng 3 (Kg);
• Trái = Phải : heo nặng 2 (Kg);
• Trái < Phải : heo nậng 1 (Kg);

Cân một lần và sử dụng 2 quả cân, nên tốn đúng 2 đồng.