{"raw_statement":[{"iden":"statement","content":"We define a function $f(x)$ over all non-negative integer $x$ as follows:\n$$\nf(x) =\n\\begin{cases}\n1 & (x = 0) \\\\\nf(\\frac{x}{3}) + 1 & (x > 0\\land x\\bmod3 = 0) \\\\\nf(x - 1) + 1  & (x > 0\\land x\\bmod 3\\neq 0)\n\\end{cases}\n$$\nCalculate $\\max_{x = l} ^ r f(x)$.\n\nYou need to answer $T$ queries independently."},{"iden":"input","content":"The first line contains a single integer $T$ ($1\\leq T\\leq 10 ^ 4$).\n\nEach of the next $T$ lines contains two integers $l$ and $r$ ($1\\leq l\\leq r\\leq 10 ^ {18}$), representing a query."},{"iden":"output","content":"Output $T$ lines. The $i$-th line contains a single integer, representing the answer to the $i$-th query."},{"iden":"note","content":"**Source**: The 2022 ICPC Asia Xi'an Regional Contest Problem E.\n\n**Author**: MagicSpark."}],"translated_statement":null,"sample_group":[["10\n1 2\n1 3\n1 4\n1 5\n2 3\n2 4\n2 5\n3 4\n3 5\n4 5\n","3\n3\n4\n5\n3\n4\n5\n4\n5\n5\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}