{"problem":{"name":"[ICPC 2022 Xi'an R] Find Maximum","description":{"content":"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\\n","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9362"},"statements":[{"statement_type":"Markdown","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.\n\n## Input\n\nThe 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.\n\n## Output\n\nOutput $T$ lines. The $i$-th line contains a single integer, representing the answer to the $i$-th query.\n\n[samples]\n\n## Note\n\n**Source**: The 2022 ICPC Asia Xi'an Regional Contest Problem E.\n\n**Author**: MagicSpark.","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9362","tags":["数学","贪心","2022","O2优化","数位 DP","ICPC","西安"],"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"]],"created_at":"2026-03-03 11:09:25"}}