Triple Operations
Contest: Codeforces Round 964 (Div. 4)
Difficulty rating: 1300
Tags: dp, implementation, math

On the board Ivy wrote down all integers from $$$l$$$ to $$$r$$$, inclusive.

In an operation, she does the following:

- pick two numbers $$$x$$$ and $$$y$$$ on the board, erase them, and in their place write the numbers $$$3x$$$ and $$$\lfloor \frac{y}{3} \rfloor$$$. (Here $$$\lfloor \bullet \rfloor$$$ denotes rounding down to the nearest integer).

What is the minimum number of operations Ivy needs to make all numbers on the board equal $$$0$$$? We have a proof that this is always possible.

Input format:
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The only line of each test case contains two integers $$$l$$$ and $$$r$$$ ($$$1 \leq l < r \leq 2 \cdot 10^5$$$).

Output format:
For each test case, output a single integer — the minimum number of operations needed to make all numbers on the board equal $$$0$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, we can perform $$$5$$$ operations as follows: $$$$$$ 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 .$$$$$$

Example input:
4
1 3
2 4
199999 200000
19 84

Example output:
5
6
36
263

Editorial:
Consider writing the numbers in ternary (it is like binary but instead we use three digits, and for clarity we will use "digit" in the solution instead of "bit" or "trit").
In the operation, we will add a $$$0$$$ to the end of the number $$$x$$$ and remove the last digit of $$$y$$$. For example, if $$$x=8$$$ and $$$y=11$$$, then in ternary the numbers are $$$22_{3}$$$ and $$$102_{3}$$$. After the operation, $$$x=24$$$ and $$$y=3$$$, and indeed in ternary they are $$$220_{3}$$$ and $$$10_{3}$$$. (This is because multiplying by $$$3$$$ is multiplying by $$$10_{3}$$$, and similarly dividing by $$$3$$$ is like dividing by $$$10_{3}$$$.)
This means that the total number of digits across all numbers does not change (since we add one digit and remove one digit). So how is it possible to make all numbers $$$0$$$?
Well, there is one exception to the above rule: when we use the operation with $$$x=0$$$, we add a $$$0$$$ to the end of the number $$$0$$$, but this added digit doesn't count (because $$$3 \cdot 0 = 0$$$). This means that if we ever do the operation with $$$x=0$$$, then we will lose one digit total (since $$$x$$$ doesn't gain a digit, but $$$y$$$ loses a digit).
This means the solution is as follows: first, we make one of the numbers equal to $$$0$$$. Then, we will use this $$$0$$$ to remove all the digits of all other numbers. To use the fewest number of operations possible, we should do the first step on the minimum number, since it has the fewest digits.
Let $$$f(x)$$$ denote the number of ternary digits in the number $$$x$$$ (actually, $$$f(x) = \lfloor \log_3 (x) \rfloor + 1$$$). Then the first step takes $$$f(l)$$$ operations (since $$$l$$$ is the smallest number in the range $$$[l, r]$$$), and the second step takes $$$f(l) + \cdots + f(r)$$$ operations (since we need to remove all the digits, which is the total number of digits from $$$l$$$ to $$$r$$$).
This means the answer for each test case is $$$f(l) + f(l) + \cdots + f(r)$$$. To find this sum quickly, we can compute prefix sums on $$$f$$$ so that the answer is simply $$$f(l) + \mathrm{psum}(r) - \mathrm{psum}(l-1)$$$, which takes $$$\mathcal{O}(1)$$$ time per test case with $$$\mathcal{O}(n)$$$ precomputation.