{"raw_statement":[{"iden":"statement","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."},{"iden":"input","content":"There 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$)."},{"iden":"output","content":"For each test case output one line containing one integer indicating the minimum number of operations to make $a$ or $b$ or both equal $1$."},{"iden":"note","content":"For 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)$."}],"translated_statement":null,"sample_group":[["5\n4 7\n9 8\n32 84\n11 35\n2 1\n","2\n7\n5\n4\n0\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}