问题描述

Ivy 在黑板上写下了从 ~l~ 到 ~r~（含两端）的所有整数。

在一次操作中，她执行以下步骤：

• 选择黑板上的两个数 ~x~ 和 ~y~，擦掉它们，并在它们的位置写上 ~3x~ 和 ~\lfloor \frac{y}{3} \rfloor~。（这里 ~\lfloor \bullet \rfloor~ 表示向下取整到最近的整数）。

要使黑板上所有数都等于 ~0~，Ivy 至少需要多少次操作？我们可以证明这总是可行的。

输入

第一行包含一个整数 ~t~（~1 \leq t \leq 10^4~）——测试用例的数量。

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

输出

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

样例输入

4
1 3
2 4
199999 200000
19 84

样例输出

5
6
36
263

说明

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

$$\displaystyle 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 . $$