← 返回题目列表

Codeforces · 1999/E

E. 三重操作

中文机器翻译题面 查看原题

在黑板上,Ivy 写下了从 $$$l$$$ 到 $$$r$$$(含)的所有整数。

在一次行动中,她执行以下操作:

- 在黑板上选择两个数字 $$$x$$$ 和 $$$y$$$,将其擦除,然后在其位置写入数字 $$$3x$$$ 和 $$$\lfloor \frac{y}{3} \rfloor$$$。 (这里 $$$\lfloor \bullet \rfloor$$$ 表示向下舍入到最接近的整数)。

Ivy 需要最少多少次操作才能使棋盘上的所有数字等于 $$$0$$$?我们有证据表明这总是可能的。

输入

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

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

输出

对于每个测试用例,输出一个整数 - 使板上所有数字等于 $$$0$$$ 所需的最少运算次数。

示例

输入 #1

4
1 3
2 4
199999 200000
19 84

输出 #1

5
6
36
263

注意

在第一个测试用例中,我们可以执行 $$$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 .$$$$$$