{"problem":{"name":"J. Good Coins","description":{"content":"It was a beautiful day, the sun was shining, the sky was clear and king Omar was listening to the birds peacefully under his favorite apple tree. Suddenly, an apple fell down and hit his head, and an ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":65536},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10102J"},"statements":[{"statement_type":"Markdown","content":"It was a beautiful day, the sun was shining, the sky was clear and king Omar was listening to the birds peacefully under his favorite apple tree. Suddenly, an apple fell down and hit his head, and an idea came to him, he decided to reduce the types of coins in his kingdom to two types only. To take a wise choice, he had to choose good coins. We call a group of two coins good if we can exchange any integer amount of money by using them. For example, you can exchange any amount of money by using coins which have the values 3 and 4 so the group {3, 4} is good but you can’t exchange the amount 3 if the two coins have the values 2 and 6, so the group {2, 6} isn’t good.  You are about to help king Omar to choose a good group of coins to be the national coins from a set of choices.  You program have to test T group of two members where 0<T<5000, and print “GOOD” if the group is good, and “NOT GOOD” if it is not.\n\nThe first line of the input contains T the number of test cases, followed by T lines, each line contains tow integers x,y separated by a space and 0 < x,y  ≤  10 ^{} 7\n\nFor each line of the input print “GOOD” if {x,y} is good and “NOT GOOD” if it is not.\n\nIf someone X wants to give another one Y the amount 4 and the available coins have the values 3 and 5, then X can give Y 8 coins of the value 5 and Y give X 12 coins of the value 3 . 8x5-12x3=4\n\n## Input\n\nThe first line of the input contains T the number of test cases, followed by T lines, each line contains tow integers x,y separated by a space and 0 < x,y  ≤  10 ^{} 7\n\n## Output\n\nFor each line of the input print “GOOD” if {x,y} is good and “NOT GOOD” if it is not.\n\n[samples]\n\n## Note\n\nIf someone X wants to give another one Y the amount 4 and the available coins have the values 3 and 5, then X can give Y 8 coins of the value 5 and Y give X 12 coins of the value 3 . 8x5-12x3=4","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case:  \n- Let $ n \\in \\mathbb{Z} $ denote the number of shops, with $ 1 < n < 100 $.  \n- Let $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of integers, where $ 1 \\le a_i \\le 10^6 $.  \n- For each $ a_i $, define its *power increment* as $ p_i = v_2(a_i) $, the 2-adic valuation: the highest integer $ k $ such that $ 2^k \\mid a_i $.  \n\n**Constraints**  \n1. $ 1 \\le T \\le \\text{unspecified} $  \n2. For each test case:  \n   - $ 1 < n < 100 $  \n   - $ 1 \\le a_i \\le 10^6 $ for all $ i \\in \\{1, \\dots, n\\} $  \n3. The selected sequence of upgrades must have strictly increasing energies: if $ a_{i_1}, a_{i_2}, \\dots, a_{i_k} $ are chosen with $ i_1 < i_2 < \\dots < i_k $, then $ a_{i_1} < a_{i_2} < \\dots < a_{i_k} $.  \n\n**Objective**  \nMaximize the sum of power increments over all selected upgrades:  \n$$\n\\max \\sum_{j=1}^k p_{i_j}\n$$  \nsubject to the constraint that the selected energies $ a_{i_1} < a_{i_2} < \\dots < a_{i_k} $ form a strictly increasing subsequence.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10102J","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}