{"problem":{"name":"[ICPC 2021 Nanjing R] Xingqiu's Joke","description":{"content":"Once again, Xingqiu hides Chongyun's ice cream into a box with a strange lock. Liyue's summer has been always very hot and Chongyun suffers more because of his excessive yang (positive) energy, so he ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9849"},"statements":[{"statement_type":"Markdown","content":"Once again, Xingqiu hides Chongyun's ice cream into a box with a strange lock. Liyue's summer has been always very hot and Chongyun suffers more because of his excessive yang (positive) energy, so he needs that ice cream desperately.\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/2dtcr426.png)\n\nThere are two integers $a$ and $b$ on the lock. Chongyun can perform the following three types of operations any number of times:\n- Minus $1$ from both $a$ and $b$;\n- Plus $1$ to both $a$ and $b$;\n- Divide both $a$ and $b$ by one of their common $\\textbf{prime}$ factor (that is to say, divide them by a $\\textbf{prime}$ $g$ where $a$ and $b$ are both divisible by $g$).\n\nThe box will be unlocked if either $a$ or $b$ or both become $1$. To help Chongyun gets the ice cream back as quickly as possible, please tell him the minimum number of operations needed to unlock the box.\n\n## Input\n\nThere are multiple test cases. The first line of the input contains an integer $T$ ($1 \\le T \\le 300$) indicating the number of test cases. For each test case:\n\nThe first and only line contains two integers $a$ and $b$ ($1 \\le a, b \\le 10^9$, $a \\ne b$).\n\n## Output\n\nFor each test case output one line containing one integer indicating the minimum number of operations to make $a$ or $b$ or both equal $1$.\n\n[samples]\n\n## Note\n\nFor the first sample test case, the optimal way is $(4, 7) \\rightarrow (3, 6) \\rightarrow (1, 2)$.\n\nFor the second sample test case, the optimal way is to apply the first type of operation $7$ times.\n\nFor the third sample test case, the optimal way is $(32, 84) \\rightarrow (16, 42) \\rightarrow (15, 41) \\rightarrow (14, 40) \\rightarrow (13, 39) \\rightarrow (1, 3)$.\n\nFor the fourth sample test case, the optimal way is $(11, 35) \\rightarrow (12, 36) \\rightarrow (6, 18) \\rightarrow (2, 6) \\rightarrow (1, 3)$.","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9849","tags":["数学","递推","2021","Special Judge","O2优化","最大公约数 gcd","ICPC","南京"],"sample_group":[["5\n4 7\n9 8\n32 84\n11 35\n2 1\n","2\n7\n5\n4\n0\n"]],"created_at":"2026-03-03 11:09:25"}}