410692: GYM104077 E Find Maximum

We define a function $$$f(x)$$$ over all non-negative integer $$$x$$$ as follows: $$$$$$ f(x) = \begin{cases} 1 & (x = 0) \\ f(\frac{x}{3}) + 1 & (x > 0\land x\bmod3 = 0) \\ f(x - 1) + 1 & (x > 0\land x\bmod 3\neq 0) \end{cases} $$$$$$ Calculate $$$\max_{x = l} ^ r f(x)$$$.

You need to answer $$$T$$$ queries independently.

The first line contains a single integer $$$T$$$ ($$$1\leq T\leq 10 ^ 4$$$).

Each of the next $$$T$$$ lines contains two integers $$$l$$$ and $$$r$$$ ($$$1\leq l\leq r\leq 10 ^ {18}$$$), representing a query.

Output $$$T$$$ lines. The $$$i$$$-th line contains a single integer, representing the answer to the $$$i$$$-th query.

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