Maximum (f(x)) in a Range

We define a function \(f(x)\) for every non-negative integer \(x\) as follows:

\[ f(x)=\begin{cases} 1 & (x=0)\\ f\Bigl(\frac{x}{3}\Bigr)+1 & \text{if } x>0 \text{ and } x \bmod 3 = 0\\ f(x-1)+1 & \text{if } x>0 \text{ and } x \bmod 3 \neq 0 \end{cases} \]

It can be shown that for \(x>0\), \(f(x)= (\text{number of digits of }x\text{ in base }3) + (\text{sum of its digits in base }3)\) and by definition \(f(0)=1\).

Your task is to answer \(T\) independent queries. In each query you are given two non-negative integers \(l\) and \(r\) (with \(l \le r\)). Find the value of \[ \max_{x=l}^{r} f(x). \]

inputFormat

The first line contains a single integer \(T\) representing the number of queries. Each of the next \(T\) lines contains two non-negative integers \(l\) and \(r\) (\(l\le r\)).

T
l1 r1
l2 r2
... 
lT rT

outputFormat

For each query, print one line containing the maximum value of \(f(x)\) for \(x\) in the range \([l, r]\).

sample

1
0 0

1