本题为 的 Hard 版本。请注意本题输出与其不同。

题目描述

对于任意非负整数 $x$，定义函数 $f(x)$：

$$f(x)= \begin{cases} 1 & (x=0)\\ f(\lfloor\frac{x}{3}\rfloor)+1 & (x>0 \text{ 且 } x \bmod 3=0)\\ f(x-1)+1 & (x>0 \text{ 且 } x \bmod 3 \ne 0) \end{cases}$$

其中 $\lfloor\cdot\rfloor$ 代表向下取整运算，$\bmod$ 代表取模运算。

你需要计算 $\max_{x=l}^r f(x)$ 的值。

你需要独立回答 $T$ 次询问。

题目格式

输入格式

首行包含一个整数 $T(1\le T\le 10^4)$，表示询问次数。

接下来 $T$ 行，每行包含两个整数 $l,r(1\le l\le r\le 10^{18})$。

输出格式

输出 $T$ 行，每行包含一个整数，表示询问答案。

样例

10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

3
3
4
5
3
4
5
4
5
5

备注

题目来源：2022 ICPC西安E题