在黑板上,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 .$$$$$$