964E

Question:

E. Triple Operations

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

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

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

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

Example

Input

Copy

4
1 3
2 4
199999 200000
19 84

Output

Copy

5
6
36
263

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

[964E.md](https://codeforces.com/contest/1999/problem/E)

My think:

At first, I thought it was a simple simulation problem: calculate the number of times x when the smallest
number divided by 3 equals 0, and then the answer would be x * 2 plus the number of remaining times when
the left number divided by 3 equals 0. However, this approach is incorrect.

By utilizing the characteristics of exponential growth and performing some simple
calculations, we can quickly determine the minimum number of operations within a given range.
This method has a low time complexity and can efficiently handle large input ranges.

Code:

import math
t = int(input())
for i in range(t):
    num = list(map(int, input().split()))
    l = num[0]
    r = num[1]
    start_pow3 = 1
    cnt_start = 1
    while start_pow3 <= (l / 3):
        start_pow3 *= 3
        cnt_start += 1
    ans = cnt_start
    pow3 = start_pow3
    next_pow3 = start_pow3 * 3
    while pow3 <= r:
        ans += (min(r + 1, next_pow3) - max(l, pow3)) * cnt_start
        cnt_start += 1
        pow3 *= 3
        next_pow3 *= 3
    print(ans)

def min_operations_to_zero(n):
    operations = 0
    while n > 0:
        n = n // 3
        operations += 1
    return operations

t = int(input())
results = []
for _ in range(t):
    l, r = map(int, input().split())
    total_operations = 0
    oper = min_operations_to_zero(l)
    for n in range(l+1, r+1):
        total_operations += min_operations_to_zero(n)
    total_operations += oper*2
    results.append(total_operations)

for result in results:
    print(result)