题目描述

题面描述

Ivy 在黑板上写下了在 $l$ 到 $r$ 之间的所有整数。

在一次运算中，她做了以下操作：

• 在黑板上选出任意两个数字 $x$ 和 $y$ ，将它们擦掉，然后在它们的位置上写下数字 $3x$ 和 $\lfloor \frac{y}{3} \rfloor$ 。(这里的 $\lfloor x\rfloor$ 表示取整，即向下取整到最接近的整数）。

要使黑板上的所有数字都等于 $0$ ，Ivy 最少需要进行多少次运算？可以证明一定有解。

输入格式

第一行包含一个正整数 $t$ ( $1 \leq t \leq 10^4$ )，表示测试用例的数量。

对于每个测试用例，仅一行包含两个正整数 $l$ 和 $r$ ( $1 \leq l < r \leq 2 \cdot 10^5$ )。

输出格式

对于每个测试用例，输出一个整数，即使黑板上的所有数字等于 $0$ 所需的最少操作次数。

样例解释

在第一个测试用例中，我们可以执行 $5$ 次操作，如下：

$$1,2,3 \xrightarrow[x=1,\\,y=2]{} 3,0,3 \xrightarrow[x=0,\\,y=3]{} 1,0,3 \xrightarrow[x=0,\\,y=3]{} 1,0,1 \xrightarrow[x=0,\\,y=1]{} 0,0,1 \xrightarrow[x=0,\\,y=1]{} 0,0,0 .$$

样例

4
1 3
2 4
199999 200000
19 84

5
6
36
263

样例说明

In the first test case, we can perform $5$ operations as follows: $$$$ 1,2,3 \xrightarrow[x=1,,y=2]{} 3,0,3 \xrightarrow[x=0,,y=3]{} 1,0,3 \xrightarrow[x=0,,y=3]{} 1,0,1 \xrightarrow[x=0,,y=1]{} 0,0,1 \xrightarrow[x=0,,y=1]{} 0,0,0 . $$$$

来源

Codeforces 1999E，英文题名 Triple Operations。