E. Find Maximum
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

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 \gt 0\land x\bmod3 = 0) \\ f(x - 1) + 1 & (x \gt 0\land x\bmod 3\neq 0) \end{cases} $$$$$$ Calculate $$$\max_{x = l} ^ r f(x)$$$.

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

Input

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

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

Example
Input
10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
Output
3
3
4
5
3
4
5
4
5
5