P9362 [ICPC 2022 Xi'an R] 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.

**Source**: The 2022 ICPC Asia Xi'an Regional Contest Problem E. **Author**: MagicSpark.