{"problem":{"name":"LCM of GCDs","description":{"content":"We have a red bag, a blue bag, and $N$ card packs. Initially, both bags are empty. Each card pack contains two cards with integers written on them. We know that the $i$\\-th card pack contains a card w","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc124_c"},"statements":[{"statement_type":"Markdown","content":"We have a red bag, a blue bag, and $N$ card packs. Initially, both bags are empty. Each card pack contains two cards with integers written on them. We know that the $i$\\-th card pack contains a card with $a_i$ and another with $b_i$.\nFor each card pack, we will put one of its cards in the red bag, and the other in the blue bag.\nAfter we put all cards in the bags, let $X$ be the greatest common divisor of all integers written on cards in the red bag. Similarly, let $Y$ be the greatest common divisor of all integers written on cards in the blue bag. Our score will be the least common multiple of $X$ and $Y$.\nFind the maximum possible score.\n\n## Constraints\n\n*   All values in input are integers.\n*   $1 \\leq N \\leq 50$\n*   $1 \\leq a_i, b_i \\leq 10^9$\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$a_1$ $b_1$\n$\\vdots$\n$a_N$ $b_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc124_c","tags":[],"sample_group":[["2\n2 15\n10 6","10\n\n*   One optimal move is to put the card with $2$ in the red bag, the card with $15$ in the blue bag, the card with $6$ in the red bag, and the card with $10$ in the blue bag.\n*   Then, the greatest common divisor of all integers written on cards in the red bag will be $2$, and the greatest common divisor of all integers written on cards in the blue bag will be $5$.\n*   The score here will be $10$."],["5\n148834018 644854700\n947642099 255192490\n35137537 134714230\n944287156 528403260\n68656286 200621680","238630"],["20\n557057460 31783488\n843507940 794587200\n640711140 620259584\n1901220 499867584\n190122000 41414848\n349507610 620259584\n890404700 609665088\n392918800 211889920\n507308870 722352000\n156850650 498904448\n806117280 862969856\n193607570 992030080\n660673950 422816704\n622015810 563434560\n207866720 316871744\n63057130 117502592\n482593010 366954816\n605221700 705015552\n702500790 900532160\n171743540 353470912","152594452160"]],"created_at":"2026-03-03 11:01:14"}}