{"code":"k12","name":"Gấp hạc","description":"**TRÍ** không như các bạn con trai khác, **TRÍ** rất thích xếp hạc giấy. \r\n\r\nVì thế trong dịp tháng **COLD HOLD**, **KHÔI** đã tặng cho **TRÍ** một tờ giấy xếp hạc kích thước $n \\times m$ (dọc $n$ cm, ngang $m$ cm). \r\n\r\n**TRÍ** rất vui khi có phần quà này và hứa sẽ gấp ra $1$ số con hạc giống hệt nhau **mà không bỏ phí một mảnh giấy nào**. \r\n\r\n![](https://i.imgur.com/BgTPf50.png)\r\n\r\nTuy nhiên, **TRÍ** đang chuẩn bị cho kỳ thi kết thúc học phần cho nên **TRÍ** muốn gấp số con hạc là nhỏ nhất.\r\n\r\nBiết rằng, để gấp một con hạc giấy bạn cần một mảnh giấy hình vuông. Và để xếp những con hạc giống nhau thì những hình vuông (chiều dài cạnh là số nguyên) đó cũng phải giống nhau, tất nhiên phải dùng kéo để cắt chúng ra.\r\n\r\n#### Input\r\n- Số nguyên dương $t (t \\leq 1000)$ - số test.\r\n- Mỗi test chứa $2$ số nguyên dương $n, m(n, m \\leq 1000)$\r\n\r\n#### Output \r\n- Số con hạc phải gấp.\r\n\r\n#### Example\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        2\r\n        2 2\r\n        6 9 \r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        1\r\n        6\r\n        ```","points":100.0,"partial":false,"time_limit":1.0,"memory_limit":655360,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}