题目描述

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.

题目大意

题目描述

定义在所有非负整数 $x$ 上的函数 $f(x)$ 如下：

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

计算 $\max_{x = l} ^ r f(x)$。

共有 $T$ 组数据。

$1\leq T\leq 10 ^ 4$，$1\leq l\leq r\leq 10 ^ {18}$。

输入格式

第一行一个整数 $T$。

接下来 $T$ 行，每行两个整数 $l, r$ 表示一组询问。

输出格式

对于每组询问，输出一行一个整数表示答案。

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

提示

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

Author: MagicSpark.