Skip to content
TheChatArchiveThe Chat Archive
DeepSeekDeepseek v3.2· deepseekHugging Face Frontier Reasoning Traces

Alexander is a well-known programmer. Today he decided to finally go out and play…

  1. User

    Alexander is a well-known programmer. Today he decided to finally go out and play football, but with the first hit he left a dent on the new Rolls-Royce of the wealthy businessman Big Vova. Vladimir has recently opened a store on the popular online marketplace "Zmey-Gorynych", and offers Alex a job: if he shows his programming skills by solving a task, he'll work as a cybersecurity specialist. Otherwise, he'll be delivering some doubtful products for the next two years.

    You're given n positive integers a_1, a_2, ..., a_n. Using each of them exactly at once, you're to make such sequence b_1, b_2, ..., b_n that sequence c_1, c_2, ..., c_n is lexicographically maximal, where c_i=GCD(b_1,...,b_i) - the greatest common divisor of the first i elements of b.

    Alexander is really afraid of the conditions of this simple task, so he asks you to solve it.

    A sequence a is lexicographically smaller than a sequence b if and only if one of the following holds:

    • a is a prefix of b, but a ≠ b;
    • in the first position where a and b differ, the sequence a has a smaller element than the corresponding element in b. Input

    Each test contains multiple test cases. The first line contains the number of test cases t (1 ≤ t ≤ 10^3). Description of the test cases follows.

    The first line of each test case contains a single integer n (1 ≤ n ≤ 10^3) — the length of the sequence a.

    The second line of each test case contains n integers a_1,...,a_n (1 ≤ a_i ≤ 10^3) — the sequence a.

    It is guaranteed that the sum of n over all test cases does not exceed 10^3.

    Output

    For each test case output the answer in a single line — the desired sequence b. If there are multiple answers, print any.

    Example

    Input

    7 2 2 5 4 1 8 2 3 3 3 8 9 5 64 25 75 100 50 1 42 6 96 128 88 80 52 7 5 2 4 8 16 17

    Output

    5 2 8 2 1 3 9 3 8 100 50 25 75 64 42 128 96 80 88 52 7 17 2 4 8 16

    Note

    In the first test case of the example, there are only two possible permutations b — [2, 5] and [5, 2]: for the first one c=[2, 1], for the second one c=[5, 1].

    In the third test case of the example, number 9 should be the first in b, and GCD(9, 3)=3, GCD(9, 8)=1, so the second number of b should be 3.

    In the seventh test case of the example, first four numbers pairwise have a common divisor (a power of two), but none of them can be the first in the optimal permutation b.

  2. DeepSeek Assistant

    We need to generate a permutation b of given numbers a_i such that the sequence c_i = gcd(b_1,...,b_i) is lexicographically maximal.

    We need to understand lexicographic order on sequence c. c is non-increasing (since adding numbers can only reduce or keep gcd). Indeed gcd of prefix is non-increasing.

    Goal: maximize the lexicographic order of c.

    We can think of constructing b step by step, selecting each b_j to maximize the resulting c sequence.

    Lexicographically maximal: we want first element c_1 as large as possible, because first element is most significant. c_1 = b_1, so we should pick the maximum number from a? Not exactly, because b_1 is just one number, and c_1 = b_1 itself. So to maximize c_1, we would want the maximum possible b_1 among all a_i. However, note that we could also have b_1 that yields same c_1? Actually b_1 is the element itself, so c_1 = b_1. So we want the largest element. So b_1 should be the maximum of a.

    But let's verify with examples: test case 4: a = [64,25,75,100,50]. According to this, max is 100, indeed output: 100 50 25 75 64. So b_1=100. test case 3: a = [3,8,9]; max =9, output: 9 3 8. So yes. test case 2: a = [1,8,2,3]; max =8, output: 8 2 1 3. So b_1 = 8. test case 7: a = [2,4,8,16,17]; max=17, output: 17 2 4 8 16. So indeed b_1 = max.

    But what if there are multiple numbers with same max? any will do.

    So first step: b_1 = max(a).

    Now we need to choose b_2, b_3,... to maximize the rest of c given that b_1 is fixed. However, note that choices after first affect c_2, c_3, etc. Lexicographic order compares after fixing the first element. So we want to maximize c_2 (the second element of c) as large as possible, given b_1 fixed, then c_3, etc.

    But careful: c_2 = gcd(b_1, b_2). So to maximize c_2, we want to choose b_2 such that gcd(b_1, b_2) is as large as possible. However, we also have to consider that later choices affect c_3 etc. However, since lexicographic order: after fixing c_1 and c_2, we then compare c_3. So we can greedily maximize c_2 first, because if there are multiple b_2 giving the same maximal c_2, then we can consider subsequent steps. But it seems likely that we should pick b_2 to maximize gcd with b_1. But we must verify if any scenario where picking a slightly smaller gcd for c_2 could lead to a larger c_3 etc overall lexicographically larger? Since lexicographic order compares c_2 first among sequences with same c_1. If we pick a smaller c_2, then the entire sequence is lexicographically smaller, regardless of later values. So we must maximize c_2. So indeed we choose b_2 to maximize gcd(b_1, b_2). If there are ties, then we need to consider further steps to maximize c_3, etc.

    In general, we can build b sequentially: At step i, we have chosen b_1...b_{i-1}. Let current prefix gcd be g = gcd(b_1,...,b_{i-1}). Now we need to choose b_i from remaining numbers to maximize the resulting sequence c_i, c_{i+1}, ... But lexicographic order: after fixing c_1...c_{i-1}, we compare c_i. So we want to maximize c_i = gcd(g, b_i). However, we also need to consider future steps. If multiple b_i yield the same c_i, then we need to decide which leads to a lexicographically larger suffix. So we need to decide tie-breaking.

    Thus the problem reduces to: Starting with an empty set of used numbers, set current gcd = 0? Actually at step 1, we choose b_1 = max (largest number). Then current gcd g = b_1. For step i from 2 to n, we choose among remaining numbers the one that maximizes the new gcd = gcd(g, a). If there is a tie, we need to consider which choice leads to lexicographically maximal suffix of c (starting from position i+1). However, note that after choosing b_i, the new gcd becomes g' = gcd(g, a). The suffix c_{i+1}, c_{i+2}, ... depends on g' and remaining numbers. Since we want lexicographically maximal, we need to consider the optimal continuation from that state.

    This looks like we can do a greedy: at each step, among remaining numbers, we want to pick the one that gives the maximum possible gcd with current g. If multiple, we need to compare the future. But perhaps we can prove that any choice among those yielding the maximal gcd leads to the same lexicographic outcome? Or we need a more global approach.

    Consider we have a set of numbers, we want to arrange them to maximize the lexicographic order of prefix gcds. Another perspective: Since c is non-increasing, we want the sequence to be as high as possible at early indices. So we want to keep the gcd as high as possible for as long as possible. That suggests we should repeatedly pick numbers that share a large common factor with the current gcd.

    This is reminiscent of a known problem: "Make lexicographically largest gcd sequence" maybe solution: repeatedly pick the number that maximizes the gcd with current prefix.

    But we must ensure tie-breaking works. Let's test with examples where tie occurs.

    Suppose we have numbers: [6, 10, 15]. b_1 = 15 (max). Now g=15. For b_2, we compute gcd(15,6)=3, gcd(15,10)=5. So max is 5, so choose 10. Then remaining 6 gives c_3 = gcd(15,10,6)=1. Sequence c = [15,5,1]. If we instead choose 6 second, c_2=3, c_3=1 -> lexicographically smaller because 5 > 3. So the rule works.

    Now suppose we have ties: e.g., a = [8, 12, 6]. b_1 = 12? Actually max=12. b_1=12, g=12. Remaining: 8,6. gcd(12,8)=4; gcd(12,6)=6. max is 6, so choose 6. Then c_2=6, c_3=gcd(12,6,8)=2. So c = [12,6,2]. The other ordering would be [12,8,?], c_2=4, so lexicographically smaller. No tie.

    But to test tie: Suppose numbers: [10, 14, 35]. b_1 = 35, g=35. gcd(35,10)=5; gcd(35,14)=7. max is 7, pick 14. Then remaining 10 gives gcd=5? Actually c_3 = gcd(35,14,10)=1. So c=[35,7,1]. If we pick 10 second, c_2=5, c_3=1 -> smaller.

    Now find a scenario where two numbers give same gcd with current g. For instance, a = [8, 12, 16]. b_1=16. g=16. Remaining: 8,12. gcd(16,8)=8; gcd(16,12)=4. So max is 8, pick 8. No tie.

    Let's construct a tie: Suppose b_1=18, remaining numbers: 6,12? gcd(18,6)=6; gcd(18,12)=6. Both give 6. So we have tie. Then we need to decide which leads to better suffix. Let's test: numbers: 18,6,12. Our set: [18,6,12]. b_1=18. For b_2, both 6 and 12 give gcd=6. If we pick 6, then remaining 12: new g' = gcd(18,6)=6; then c_3 = gcd(6,12)=6. So c = [18,6,6]. If we pick 12 second, then g'=gcd(18,12)=6; remaining 6: c_3=gcd(6,6)=6. So both yield same c sequence: [18,6,6]. So tie doesn't matter.

    But what about numbers that later produce different c_3? Since after picking a number that gives same gcd, the new gcd g' is the same (gcd(g, a) = same value for both). Actually if both numbers produce the same gcd with g, then g' = d, same for both. So after that step, the set of remaining numbers is the same (just one different number left), but g' is same. However, the remaining numbers may be different because we removed different numbers. Could that affect c_3? Yes, because c_3 = gcd(g', b_3). If the remaining numbers differ, c_3 might differ. In the above example, both remaining numbers gave same gcd with g' (6 and 6). But it could be that one remaining number yields a larger c_3 than the other. So we need to consider which removal yields a larger c_3, given that g' is fixed. Since we want to maximize lexicographically, after fixing c_1 and c_2, we want to maximize c_3. So among the choices that maximize c_2, we should choose the one that leads to the maximal possible c_3, and so on.

    Thus we need to solve: Starting with multiset S of numbers, and current gcd g, we want to choose an ordering that yields lexicographically maximal sequence c.

    We can model it as: At each step, we need to choose a number from S to maximize the pair (new_g, suffix) lexicographically, where new_g = gcd(g, a). Since we compare sequences, the priority is to maximize new_g. If tie, we need to compare the best possible suffix starting with new_g and remaining S{a}. This suffix is the optimal sequence we can get from that state. So it's recursive.

    Given n ≤ 1000 total sum across test cases, we could potentially do a DP or greedy with simulation.

    But note constraints: each a_i ≤ 1000, sum n ≤ 1000. So we could afford O(n^2 * log(max)) or even O(n^2 * something). But maybe there is a simpler greedy that always works: At each step, pick the number that maximizes gcd(g, a). If multiple, pick the largest number? Or maybe it's always safe to pick any that gives the maximal gcd because the subsequent gcds won't be larger than that anyway? Let's think.

    Suppose g current. If we pick a and b both yield same d = gcd(g, a) = gcd(g, b). Then after that, we have new g' = d. Now the future sequence depends on the set of remaining numbers. The question: Among the candidates that give the same d, which one to remove? Could it affect the possibility to get larger c_i later? Since later c_i will be gcd(d, some set) which is at most d. Actually d is the gcd of g and the chosen number, but after that, the gcd can only stay the same or decrease. So the next c_3 will be ≤ d. So the maximum possible c_3 is at most d. So if we can achieve c_3 = d (i.e., keep gcd at d for the next step) that would be best. If we cannot keep it d, then we get something less.

    Given two different removed numbers, the remaining sets differ. We want to maximize the lexicographic suffix starting from step i+1 with current gcd = d. This suffix is determined solely by the multiset of remaining numbers and d. So we should choose the removal that yields the lexicographically larger suffix. That seems like we need to compute the optimal ordering from a state. But perhaps we can argue that any removal that yields maximal d also yields the same optimal suffix? Not necessarily.

    Consider example: S = {g=12, remaining numbers: 8, 6? Actually b_1=12? Let's create a scenario with g=12 and numbers: 4 and 8? gcd(12,4)=4, gcd(12,8)=4 both give 4. So g=12, S = {4,8}. If we pick 4 first, new g'=4, remaining {8}: c_3 = gcd(4,8)=4. So c = [12,4,4]. If we pick 8 first, new g'=4, remaining {4}: c_3=gcd(4,4)=4. Same. So no difference.

    We need an example where the remaining numbers after removal produce different c_3. For that, we need two numbers a and b such that gcd(g, a)=gcd(g, b)=d, but the remaining number (the one not chosen) when taken with d gives different gcd. Since there are only two numbers left, c_3 will be gcd(d, x) where x is the remaining number. So if we choose a to remove, remaining is b, c_3 = gcd(d, b). If we choose b, remaining is a, c_3 = gcd(d, a). Since both a and b yield same d with g, it's possible that gcd(d, a) != gcd(d, b). For example, let g=30, a=10, b=15. gcd(30,10)=10, gcd(30,15)=15? Actually 30 and 15 give 15, not same. Let's find numbers such that both give same d. Suppose g=12, a=4 gives 4, b=8 gives 4 (since gcd(12,8)=4). Then d=4. Then if we remove a, remaining b=8, c_3 = gcd(4,8)=4. If we remove b, remaining a=4, c_3 = gcd(4,4)=4. So same.

    What about g=18, a=6 -> 6, b=12 -> 6. Then d=6. If remove a, remaining 12 gives gcd(6,12)=6; if remove b, remaining 6 gives gcd(6,6)=6. Same. In general, if both a and b have the property that gcd(g, a)=d and gcd(g, b)=d, does it imply that gcd(d, a)=d? Not necessarily. Actually gcd(d, a) could be less than d. Because d divides g, and a may have extra factors not in g? Wait: if d = gcd(g, a), then d divides a. So a is a multiple of d. Similarly b is multiple of d. So both a and b are multiples of d. Then gcd(d, a) = d because d divides a. Since d | a, gcd(d, a) = d. Similarly gcd(d, b) = d. So indeed, if a is a multiple of d, then gcd(d, a) = d. Because d's prime factors are all in a? Actually d divides a, so a = d * k, so gcd(d, d*k) = d. So indeed, gcd(d, a) = d. So if we have two numbers a and b both giving same d = gcd(g, a) = gcd(g, b), then both are multiples of d. Therefore, for the remaining number x, we have gcd(d, x) = d (since x is also multiple of d). So c_3 will always be d. So if only two numbers left after picking one, c_3 will be d regardless. That suggests that when only two numbers remain after this step, tie-breaking doesn't matter. But what if there are more numbers remaining? For step i, after we choose a number, we still have more than one number left. Then the suffix is not just a single number but a sequence. So tie-breaking could matter.

    Consider we have g, and three remaining numbers: a, b, c, where both a and b give same d = gcd(g, a) = gcd(g, b), but c maybe gives a smaller gcd. After choosing either a or b, we have new g' = d, and remaining set = the other two numbers. The subsequent optimal ordering from that state may differ because the set of numbers left is different (one swapped). Since both a and b are multiples of d, but they may differ in other ways, affecting future steps after we add the other numbers.

    For example, let's construct such a case. We need g, and at least three numbers: two numbers a,b that give same d with g, and a third number c. After picking a, we have remaining {b, c}; after picking b, we have {a, c}. The suffix (starting from step i+1) with gcd d might yield different c_{i+1} values depending on which of a and b we removed.

    We need to see if it's possible that the optimal suffix from state (d, {b,c}) is lexicographically different from (d, {a,c}). If so, we need to choose the removal that yields lexicographically larger suffix.

    Let's try to find concrete numbers. Let g = 30. We want two numbers a,b such that gcd(30, a) = gcd(30, b) = d. d could be 6,10,15, etc. Also we need a third number c. And we need the subsequent lexicographic sequences to differ.

    Say g=30, d=6. Which numbers a have gcd(30, a)=6? They must be multiples of 6 but not divisible by 5? Because gcd with 30 = 6 means that they are divisible by 2 and 3, but not by 5. So numbers like 6, 12, 18, 24, 36, etc. Let's choose a=12, b=18. Both give gcd(30,12)=6? gcd(30,12)=6, yes. gcd(30,18)=6. Also maybe a=6 gives 6 too. So a=12, b=18. Then let c be something else, say c=10 (gcd(30,10)=10). But we want to see suffix differences after picking either a or b. Suppose we are at step with g=30, remaining S={12,18,10}. We'll choose b_2. Candidates: 12 gives d=6, 18 gives d=6, 10 gives d=10. Since we want to maximize c_2, we pick max d=10? Actually d=10 >6, so we would pick 10 first, not a tie among 12 and 18. So to have tie for max, we need that both a and b give the maximum possible d, and that d is the highest among all candidates. So we need that all numbers that give higher d (like 10) are not present, or also give same d? Actually we need to consider the step where the maximum d is achieved by multiple numbers. So we need that the maximum possible gcd(g, x) for x in remaining set is d, and that there are at least two numbers achieving d. So we need all numbers that give larger d than d are not present, or if present, they would be chosen first. So in that step, the top value d is achieved by multiple numbers. So we need to ensure no number gives a gcd > d.

    So let's try to craft: g=30, d=6 is not max because 10 gives 10>6. So we need numbers that achieve the same max. Let's aim for d=10 as max. Which numbers give gcd(30, x)=10? They must be multiples of 10 but not of 3? Actually 30=235. For gcd to be 10=2*5, the number must be divisible by 2 and 5, but not by 3. So numbers: 10, 20, 40, 50, etc. So choose a=10, b=20. Both give 10. Then c maybe something that gives less, say c=6 gives 6. So S={10,20,6} with g=30. Now step: we need to pick b_2. Candidates: 10 gives d=10, 20 gives d=10, 6 gives d=6. So max d=10, tie between 10 and 20. Now after picking either 10 or 20, g' becomes 10, and remaining numbers: if pick 10, remaining {20,6}; if pick 20, remaining {10,6}. Now we need to compute the optimal suffix from state (g'=10, set T). The suffix sequence of c from step 3 (i.e., c_3, c_4) will be determined by ordering of remaining numbers to maximize lexicographic sequence starting with gcd=10. Since we will choose the next number to maximize gcd with 10, etc.

    Let's compute both scenarios:

    Scenario A: pick 10 first, then g=10, remaining {20,6}.

    • Next step: compute gcd(10,20)=10, gcd(10,6)=2. Max=10, so pick 20. Then g becomes 10, remaining {6}, c_3=10. Then final c_4 = gcd(10,6)=2. So c sequence: c1=30, c2=10, c3=10, c4=2. Scenario B: pick 20 first, then g=10, remaining {10,6}.
    • Next: gcd(10,10)=10, gcd(10,6)=2. Max=10, pick 10. Then g stays 10, c3=10. Then final: gcd(10,6)=2. So c: 30,10,10,2.

    Both yield same sequence: [30,10,10,2]. So tie.

    We need to see if any scenario yields different. Suppose numbers: g=30, candidates achieving d=6 (since max d=6 maybe?), but then we need to ensure no number gives >6, i.e., no number divisible by 10 or 15. So numbers like 12,18,24, etc. But then d=6 is the max. Example: S={12,18,24}. All give gcd(30, x)=6? gcd(30,12)=6, gcd(30,18)=6, gcd(30,24)=6. So all three give same d=6. But then picking any gives g'=6, and remaining two numbers are both multiples of 6, so any subsequent ordering yields c3 = gcd(6, next) which is at most 6, but since both numbers are multiples of 6, gcd(6, x) = 6 (as argued). So c3=6, then c4=6? Wait: after picking second, g=6, then remaining one gives gcd(6, that)=6. So c sequence: [30,6,6,6]. So all same.

    Seems like if all numbers are multiples of d after we have gcd d, then the sequence remains d until maybe when some numbers not multiples of d appear. But in the tie situation, the numbers that give max d are all multiples of d, and any number that gives a smaller gcd is not a multiple of d. So after we pick one of the max-d numbers, the new g'=d. The remaining set consists of some numbers that also gave d (multiples of d) and possibly numbers that gave smaller gcd. Those numbers that gave d are multiples of d, so they will keep gcd at d when taken, while numbers that gave smaller will reduce gcd. So the suffix lexicographic order will be determined by how quickly we can avoid reducing gcd. Ideally, we want to keep gcd high as long as possible. So we should postpone taking numbers that would reduce gcd. That suggests that when we have ties, we should pick among the numbers that give the max d in such a way that the set of numbers that are multiples of d (including possibly the ones we pick later) is as large as possible? Actually after picking one max-d number, we have g'=d. Among remaining numbers, those that are multiples of d will keep gcd at d when taken; those that are not will reduce gcd. The lexicographically maximal suffix would be to take all multiples of d first, then the ones that reduce gcd, because that keeps c high as long as possible. Since we will later choose numbers to maximize prefix gcds, we will indeed always pick next the number that gives the highest possible gcd with current g. That would be: among remaining numbers, the highest gcd possible is d if there is any multiple of d left; if not, then some smaller value. So the order in which we take multiples of d among themselves doesn't matter because they all give gcd d. So the crucial point is: after we have g'=d, we will first take all numbers that give gcd = d (i.e., multiples of d) before taking any that give lower gcd. So the suffix sequence will have a block of d's of length equal to the count of remaining numbers that are multiples of d, then eventually drop.

    Now if we have a tie for the current step, picking one max-d number yields that after step, the count of remaining multiples of d might differ depending on whether the chosen number is a multiple of d (it is) and whether the other candidate is also a multiple of d (it is). So after removal, the number of multiples of d remaining is the same regardless of which max-d number we remove? Not necessarily: if both candidates are multiples of d, then whichever we remove, we still have the same number of multiples of d remaining? Actually the set of remaining numbers includes all other numbers, including the other max-d numbers. So if there are k numbers (including the one we pick) that give gcd = d, after picking one, we have k-1 left. So the number of remaining multiples of d is (k-1) plus possibly other numbers that are multiples of d but originally gave lower gcd? Wait: if a number gave lower gcd with g, it may still be a multiple of d? Let's examine: d = gcd(g, a) is the maximum possible? Actually for a number to give gcd = d, it must be a multiple of d and not have extra common factors with g beyond d? But if a number is a multiple of d, then gcd(g, a) is at least d, because d divides both g and a? Actually d divides g? Since d = gcd(g, a), d must divide g. So d divides g. For any number x that is a multiple of d, gcd(g, x) could be greater than d if x shares additional prime factors with g. But we are considering that d is the maximum gcd achievable at this step. That means for any multiple of d, gcd(g, x) is either d or larger. Since we are in a tie where the maximum is d, no number gives larger than d. Therefore, any number that is a multiple of d must have gcd(g, x) ≤ d. But if x is multiple of d, gcd(g, x) ≥ d (since d divides both). So it must equal d. So all multiples of d in the set give exactly d. Conversely, any number giving d is a multiple of d. So the set of numbers that give d is exactly the set of numbers in the remaining set that are multiples of d. So count of such numbers is exactly the count of numbers achieving the max d.

    Thus, at the current step, suppose there are m numbers that achieve the max d (including the one we will pick). After picking one, we will have m-1 numbers that are multiples of d left. Also, any other numbers (non-multiples) will give lower gcd. Therefore, the suffix after this step: we will have a block of (m-1) numbers that will keep gcd = d (if we pick them next), and then eventually we will have to pick non-multiples, causing gcd to drop. So the sequence of c from step i+1 onward will be: c_{i+1} = d (if we pick a multiple), c_{i+2} = d (if we still have multiples), ..., until we exhaust multiples, then eventually lower values. The exact length of the d-block after this step is exactly the number of multiples of d remaining. Since that number is m-1 irrespective of which specific multiple we pick, the suffix's c values up to that point are determined: we will get d for the next (m-1) steps (provided we pick multiples each time). But is it guaranteed that we will always pick multiples as long as they exist? Since we are following the greedy algorithm that at each step picks the number that maximizes gcd with current g, and current g = d, and multiples of d give gcd = d, while non-multiples give < d. So the max gcd we can get at next step is d, as long as there is any multiple of d left. So we will indeed pick a multiple of d at each subsequent step while they exist, because that gives the max possible c (which is d). And if there are multiple multiples, they all give d, and we have to decide among them; but the next step's c will be d regardless. However, after picking a multiple, the count of multiples reduces by 1, but the gcd remains d. So for the next steps, again we are in a similar situation: we have some set of numbers that are multiples of d (the ones we didn't pick yet) and possibly non-multiples. As long as there is at least one multiple, the max gcd with d is d, so we will pick a multiple. The choice among multiples could affect later when we run out of multiples: the order of non-multiples may affect the later decreasing pattern. But after we exhaust all multiples of d, we will have g = d and a set of numbers that are not multiples of d. At that point, we need to continue: pick the next number that maximizes gcd(d, x). That will be some d' < d. That could depend on which specific multiples we removed? The set of non-multiples is fixed regardless of which multiples we removed, because the multiples are all numbers that were multiples of d. The set of non-multiples is exactly the numbers that gave less than d initially. So which multiples we removed doesn't affect the set of non-multiples; it only affects which multiples are left. But after we exhaust all multiples, the remaining numbers are exactly the non-multiples (plus maybe some numbers that are multiples of d but we removed them earlier? Actually all multiples of d will be removed before we start picking non-multiples, because as long as there is any multiple, we pick one. So eventually, all multiples of d will be removed. The order in which we remove them doesn't affect the set of non-multiples, which is unchanged. So after we have removed all multiples, the state is (g = d, set = non-multiples). That is independent of which specific multiples we removed first. So the suffix from the point when we start picking non-multiples is determined solely by that set of non-multiples and d. Therefore, the entire suffix after the current step is actually independent of which particular max-d number we pick now, as long as we subsequently follow the greedy (maximizing gcd at each step). Because after picking one max-d number, we will be in a state with (g = d) and a set consisting of: the remaining (m-1) multiples of d, and all non-multiples. The greedy algorithm on that state would first pick all multiples (any order) then the non-multiples. The resulting c sequence will be: (c_{i+1} = d) for each of the steps corresponding to picking a multiple (including possibly the one we just picked? Wait careful: we already accounted for the current step; after this step we have i steps done. For the suffix, the first element is c_{i+1} when we pick the next element. That will be d if we pick a multiple. Since there are (m-1) multiples left, we will get (m-1) more d's before it drops. So the sequence of c after the current step will be: (m-1) times d, then whatever sequence we get from processing non-multiples starting with gcd = d. The order in which we pick the multiples among themselves does not affect the values: each yields c = d. However, could the order of picking among multiples affect the subsequent processing of non-multiples? The gcd remains d regardless, so the state when we start non-multiples is exactly (g = d) and set of non-multiples. That is independent of which multiples we removed in which order, as long as we removed all of them. So the suffix is uniquely determined. Therefore, in the tie situation where multiple numbers give the same maximal d, the resulting c sequence after the current step is independent of which one we pick. Because the number of multiples left is the same, and the set of non-multiples is unchanged. Thus any choice yields the same suffix.

    But is there any scenario where choosing a different max-d number could change the set of non-multiples? No, because non-multiples are those numbers that are not multiples of d. The chosen max-d number is a multiple of d, so it doesn't affect the non-multiples. So the set of non-multiples remains the same. So the suffix is the same.

    Thus we can simply pick any number that yields the maximal gcd with current g, and the lexicographic result is unique. This suggests a simple greedy algorithm: start with empty sequence, initial g = 0? Actually for first step we need to maximize b_1 itself. That is equivalent to: at step 1, current g = 0 (or undefined). But we can treat as: we want to maximize c_1 = b_1. So we should pick the maximum a_i. That's consistent with the greedy: among all numbers, we want to maximize gcd(0, a)?? gcd(0, a) = a (since gcd(0,x)=|x|). So if we treat initial g=0, then gcd(0, a) = a, so maximizing that is picking the max a. So we can unify: start with g=0, and at each step pick the number among remaining that maximizes gcd(g, a). If multiple, pick any.

    But wait: is gcd(0, a) defined? Usually gcd(0, a) = a. So that's fine.

    Now we just need to implement: For each test case, given list a of n numbers, we repeatedly:

    • Let current_g = 0 initially.
    • For i from 1 to n:
      • Find the element among unused that gives the maximum value of gcd(current_g, x).
      • If multiple, choose any (e.g., the maximum x, or first found).
      • Append that element to b.
      • Update current_g = gcd(current_g, chosen).

    Complexity: O(n^2 * log(max)) if we compute gcd each time. Since sum n ≤ 1000, it's fine.

    But we need to verify with examples and edge cases. Let's test with the given examples.

    Example 1: [2,5]. current_g=0, max gcd= max(2,5)=5? Actually compute gcd(0,2)=2, gcd(0,5)=5, max=5, pick 5. Then current_g=5, remaining [2]: gcd(5,2)=1, only choice. b=[5,2] -> correct.

    Example 2: [1,8,2,3]. current_g=0 -> max gcd: max values: 8 yields 8, others less, pick 8. current_g=8. Remaining: [1,2,3]. Compute gcd: gcd(8,1)=1, gcd(8,2)=2, gcd(8,3)=1. Max=2, pick 2 (if tie maybe choose 2). current_g=2. Remaining [1,3]. gcd(2,1)=1, gcd(2,3)=1. Max=1, both tie, pick any, say 1 then 3. b=[8,2,1,3] matches output (they had 8 2 1 3). Could also be 8 2 3 1 but still valid. So works.

    Example 3: [3,8,9]. Start: max gcd with 0: pick 9 (since 9>8>3). g=9. Remaining [3,8]. gcd(9,3)=3, gcd(9,8)=1. max=3, pick 3. g=3. remaining [8]: gcd(3,8)=1. Output [9,3,8] matches.

    Example 4: [64,25,75,100,50]. start: pick 100 (max). g=100. remaining: [64,25,75,50]. gcds: gcd(100,64)=4, gcd(100,25)=25, gcd(100,75)=25, gcd(100,50)=50. max=50, pick 50. g=50. remaining [64,25,75]. gcds: gcd(50,64)=2, gcd(50,25)=25, gcd(50,75)=25. max=25, two choices (25 and 75). We can pick 25 first (or 75). If we pick 25, g=25, remaining [64,75]. gcd(25,64)=? 25 and 64 gcd=1, gcd(25,75)=25. max=25, pick 75. g=25, remaining [64], gcd=1. So b=[100,50,25,75,64] matches output. If we picked 75 first instead: g=50? Actually after picking 75, g = gcd(50,75)=25. Remaining [64,25]. gcd(25,25)=25, pick 25, g=25, then 64 yields 1. b=[100,50,75,25,64] which would give c=[100,50,25,25,1]? Wait compute: after 100,50: c2=gcd(100,50)=50. After adding 75: c3=gcd(100,50,75)=gcd(100,50,75). gcd(100,50)=50, gcd(50,75)=25? Actually gcd(100,50,75) = gcd(gcd(100,50),75) = gcd(50,75)=25. So c3=25. Then adding 25: c4=gcd(25,25)=25. Then adding 64: c5=gcd(25,64)=1. So c = [100,50,25,25,1]. In the given output, c = [100,50,25,25,1] as well? Let's compute: 100,50,25,75,64: c1=100, c2=gcd(100,50)=50, c3=gcd(100,50,25)=gcd(50,25)=25, c4=gcd(100,50,25,75)=gcd(25,75)=25, c5=gcd(...,64)=1. Same sequence. So both produce same c sequence. So tie-breaking doesn't matter.

    Example 5: [42] -> output 42.

    Example 6: [96,128,88,80,52,7]. Let's test greedy: start g=0: pick max=128. g=128. remaining [96,88,80,52,7]. Compute gcd: gcd(128,96)=32, gcd(128,88)=8? 128 and 88: 128=2^7, 88=811? Actually 88=811, gcd=8? gcd(128,88)=8 (since 128 mod 8=0, yes). gcd(128,80)=16? 80=165, 128=168 -> gcd=16. gcd(128,52)=4? 52=413, 128=432 -> 4. gcd(128,7)=1. max=32 (96). So pick 96. g= gcd(128,96)=32. remaining [88,80,52,7]. gcd(32,88)=8? 32 and 88: 32=84, 88=811 -> 8. gcd(32,80)=16? 32 and 80: gcd=16? 32=162, 80=165 -> 16. gcd(32,52)=4? 32 and 52: gcd(4? Actually gcd(32,52)=4). gcd(32,7)=1. max=16 (80). So pick 80. g= gcd(32,80)=16. remaining [88,52,7]. gcd(16,88)=8? 16 and 88: 16=82? Actually 88=811, 16=16, gcd=8? 16 and 88 share 8? 16=2^4, 88=2^311, gcd=8. gcd(16,52)=4? 16 and 52: gcd=4. gcd(16,7)=1. max=8 (88). pick 88. g= gcd(16,88)=8. remaining [52,7]. gcd(8,52)=4? 52=413, 8=4*2, gcd=4. gcd(8,7)=1. max=4 -> pick 52. g= gcd(8,52)=4. remaining [7]. gcd(4,7)=1 -> pick 7. So b = [128,96,80,88,52,7]. The output is [128,96,80,88,52,7] exactly. Good.

    Example 7: [2,4,8,16,17] greedy: start g=0, pick max=17. g=17. remaining [2,4,8,16]. gcd(17,2)=1, gcd(17,4)=1, gcd(17,8)=1, gcd(17,16)=1. All 1, tie. Pick any, say 2. g= gcd(17,2)=1. remaining [4,8,16]. gcd(1, anything)=1, so all ties. So any order yields c = [17,1,1,1,1]. The output is [17,2,4,8,16]. So that works.

    Thus greedy works.

    Now we should double-check the reasoning for ties and ensure there is no hidden counterexample.

    We argued that after picking a number that gives maximum d, the suffix is independent of which specific number we pick. But we assumed that the greedy algorithm continues to pick the number that maximizes gcd with current g at each step. That's what we plan to do. So the overall algorithm is exactly this greedy. Since we are building the sequence using the same rule recursively, it should produce an optimal sequence. The argument: at each step, to maximize lexicographic c, we need to maximize c_i. Since c_i = gcd(current_g, chosen). So we need to choose a that maximizes this value. If multiple a achieve the same maximal d, then c_i is same regardless. Then we need to maximize the suffix from state (d, S{a}). But we claim that the suffix produced by continuing the same greedy algorithm (i.e., at each step picking the number that maximizes gcd) yields the lexicographically maximal suffix from any state, and that this suffix is the same for any a that gave the same d. So picking any yields same overall sequence. But is it true that the greedy algorithm from a state yields the lexicographically maximal sequence for that state? We need to prove that the greedy approach (maximizing gcd at each step) is optimal overall, not just myopically. Usually for lexicographic optimization, a greedy approach that at each step chooses the maximum possible value for the current position is optimal if the problem has a "matroid" or "exchange" property. We need to verify that given a state (current gcd g, remaining multiset S), the optimal choice is to pick an element that maximizes gcd(g, x). Is it always optimal? Let's try to think if there could be a case where picking a slightly smaller gcd now could allow a larger gcd later, leading to a lexicographically larger sequence? Since c is non-increasing, if we pick a smaller c_i now, later c_j can never exceed c_i because sequence is non-increasing. So if we choose a smaller value now, the entire suffix will be ≤ that smaller value. While if we choose a larger value now, the suffix can be at most that larger value, but it could drop later. However, if we choose a larger value now, the best we can do later is to keep it as high as possible; if we choose a smaller value now, the maximum possible later values are bounded by that smaller value. Therefore, picking the maximum possible c_i is always beneficial lexicographically, because if we pick a smaller c_i, even if later we could keep it high, the sequence would be lexicographically smaller at position i. So indeed the optimal choice is to maximize c_i.

    But careful: What if two choices yield the same c_i (tie)? Could one choice lead to a better suffix than the other? In that case, we need to compare suffixes. So we need to determine the optimal suffix. If we can prove that the suffix is independent of which tie we pick (under the rule that we will continue greedily), then we are fine. Alternatively, we could just compute the optimal suffix recursively, but our simple greedy picks any. We must be sure that there is no scenario where two ties produce different suffix sequences, and that the greedy tie-breaking (e.g., pick largest element) might not yield the optimal suffix. However, the problem says "If there are multiple answers, print any." So we just need to output any sequence that yields lexicographically maximal c. So even if ties could produce different but still lexicographically maximal sequences (i.e., multiple optimal sequences), we can output any. So it's okay if we pick any among those that maximize c_i. But we need to ensure that picking any among those that maximize c_i always yields an optimal sequence (i.e., that there exists at least one optimal continuation among them). But we must be careful: Could it be that some choices that give the maximal c_i lead to suboptimal suffix, while another choice with same c_i leads to a better suffix, and the greedy algorithm that picks arbitrarily might accidentally pick the suboptimal one? That would be problematic because then the final c might not be lexicographically maximal. So we need to confirm that all choices that achieve the same maximal c_i lead to the same eventual c sequence (when we continue optimally). Or if they lead to different sequences, at least one is optimal, but we need to guarantee that our arbitrary choice still yields an optimal sequence. However, since we are implementing the greedy that at each step picks the maximal gcd, and if ties, we just pick any (say the first), we must verify that this overall greedy algorithm yields a lexicographically maximal c. Many participants have solved this problem, and the typical solution is exactly this greedy. So it's likely correct.

    We should try to construct a potential counterexample. Let's attempt to find numbers where multiple options with same gcd lead to different suffixes, and one suffix is lexicographically better than the other. According to our earlier reasoning, after picking a number with gcd = d, the state becomes (g' = d, remaining S' = S \ {a}). The future optimal sequence depends on S' and d. We need to see if for two different a that both give gcd(g, a) = d, the optimal suffix from (d, S{a}) can be different.

    Suppose we have g and two numbers a, b both with gcd(g, a)=gcd(g, b)=d. After picking a, we have S' = (S \ {a}) = includes b, and other numbers. After picking b, S'' = (S \ {b}) includes a. So the sets differ: one has a, the other has b. Since a and b are both multiples of d, they behave similarly with respect to d: both are multiples of d, so when processed from state with gcd=d, both will yield gcd(d, a) = d, gcd(d, b)=d. So they are identical in terms of contribution to maintaining the gcd. However, after we have taken all multiples of d, we will move to non-multiples. The set of non-multiples is unchanged, but the set of multiples left after the initial pick differs: In S', the multiples left are all original multiples except a; in S'', they are all except b. So the count of multiples left is the same (m-1). But the identity of which multiples are left could affect the later stages? When we start processing non-multiples, the gcd will drop to some d' < d. At that point, we have a set of numbers that are not multiples of d, but also maybe some multiples of d that we haven't taken? Wait, by the time we start processing non-multiples, we would have taken all multiples of d (since as long as there is any multiple, we will take it because it gives gcd = d, which is maximum possible. So we will not start non-multiples until all multiples of d are exhausted. So the set of numbers we have when we start non-multiples is exactly the non-multiples. That set is the same regardless of which specific multiples we removed earlier, because all multiples are eventually removed before we touch non-multiples. So the suffix after the point when all multiples are removed is the same. However, there could be an effect if among the multiples, some are also multiples of a larger factor that could become relevant after the gcd drops? But after we have dropped, the gcd becomes d' which is less than d. At that point, the numbers that were multiples of d might still be in the set if they were not yet taken? But we argued we will take all multiples of d before the gcd drops, because as long as there is any multiple of d, the max possible gcd with current g = d is d (since any multiple yields exactly d, and any non-multiple yields less). So we will always prefer to take a multiple to keep the gcd high. So yes, we will exhaust all multiples of d before taking any non-multiple. Therefore, after we finally take the last multiple, the gcd is still d, and then we pick a non-multiple which yields a new gcd d' = gcd(d, x) < d. At that point, the set of remaining numbers consists of the other non-multiples (since all multiples are gone). So the composition of the set when we start with gcd d' does not include any multiples of d (except maybe some that are also multiples of d'? But if a number is a multiple of d, it is automatically a multiple of any divisor of d? Actually if a number is multiple of d, then it is also multiple of d' if d' divides d? Not necessarily: d' is a divisor of d? Since d' = gcd(d, x) for some x non-multiple of d. d' divides d. So d' is a divisor of d. A number that is a multiple of d is also a multiple of d' because d' divides d, so multiple of d implies multiple of d'. So after we drop to d', the numbers that were multiples of d are still in the set? Wait, we had removed all multiples of d before the drop. So after we take the first non-multiple, we have removed all multiples of d already. So there are no multiples of d left. However, the non-multiples might include numbers that are multiples of d' but not of d. That's fine. But the point is: the set of numbers left after the drop does not contain any of the original multiples of d (since they have been removed). So the set is independent of which specific multiples were removed, because all multiples are removed. So the state after the drop is the same.

    Thus, the entire suffix of c is determined solely by the multiset of numbers and the order of processing among the multiples does not affect the sequence of c values (since they all produce d). However, one nuance: Could the order of processing the multiples affect the exact value of d' when we eventually take a non-multiple? Since d' = gcd(d, x) where x is the non-multiple we pick first. The choice of which non-multiple to pick among possibly many will determine d'. But the set of non-multiples is the same, and we will choose the one that maximizes gcd(d, x) at that step. That choice might depend on which multiples have been removed? No, because the multiples are gone, the set of non-multiples is the same. So the algorithm will pick the non-multiple that gives the maximum gcd(d, x). This is deterministic given the set. So d' is fixed regardless of which multiples were removed earlier. After that, we continue similarly.

    Thus, the suffix is indeed independent of the specific choice among max-d numbers. So any choice yields the same c sequence.

    But is it always true that after we pick a number giving gcd = d, we will always pick all remaining multiples of d before any non-multiple? That's because as long as there is at least one multiple of d left, the maximum gcd(d, x) over remaining x is at least d (since that multiple gives gcd = d). Any non-multiple gives gcd < d (since it's not multiple of d, gcd(d, x) must be a proper divisor of d). So the maximum is d. So we will pick a multiple. This holds inductively. So yes.

    Therefore the greedy algorithm is optimal and the choice among ties does not affect the final c sequence (they all yield the same c sequence). So we can just pick any.

    One more subtlety: When current g=0, we pick max number. That's consistent.

    Edge Cases: When all numbers are equal? Then gcd stays same, all choices give same.

    Thus, algorithm is straightforward: For each test case, list a. Set g=0. While list not empty, find index j that maximizes gcd(g, a[j]) (if tie, any). Append a[j] to result, remove from list, update g = gcd(g, a[j]). Complexity O(n^2 * log M) with n ≤ 1000 and total n across tests ≤ 1000, fine.

    We can implement by using a vector and marking used, or better, we can repeatedly select.

    Implementation details: t up to 1000, sum n up to 1000, so O(n^2) per test case overall O( (sum n)^2 ) = up to 1e6, fine.

    Alternatively, we can sort or use frequency but not needed.

    So code plan:

    Read t. For each test: read n, then list a. Initialize ans empty list, cur = 0. Create a list of available indices or use vector and remove. For i in range(n): best = -1, best_val = -1, best_idx = -1. For j in range(len(available)): val = gcd(cur, a[j]) if val > best_val or (val == best_val and a[j] > best? Actually any tie, but we can break ties by larger a[j] or just first.) We'll take the first max. Append a[best_idx] to ans, remove it from available, set cur = best_val. Print ans.

    But careful: we need to compute gcd quickly. Use math.gcd.

    Edge Cases: n=0? not possible.

    Check with given examples.

    Now, we might want to justify the greedy more formally, but code is simple.

    Double-check test 6: We computed and matches.

    Now, let's test some custom scenarios.

    Case: [6, 10, 15] earlier: g=0 -> pick 15 (max). cur=15. available [6,10]. gcd(15,6)=3, gcd(15,10)=5. best=5, pick 10. cur=5. available [6]. gcd(5,6)=1. ans [15,10,6] -> c = [15,5,1]. That is lexicographically maximal? Let's see if alternative ordering [15,6,10] gives c = [15,3,1] which is smaller because 5>3. So good.

    Case: [4,6,8]? Let's compute: g=0 -> pick 8. cur=8. available [4,6]. gcd(8,4)=4, gcd(8,6)=2, pick 4, cur=4. then 6 gives gcd(4,6)=2. c = [8,4,2]. Alternative [8,6,4] gives [8,2,2] which is smaller (4>2). So good.

    Case: [12,18,24,36]? g=0 -> pick 36. cur=36. gcd with others: 12->12, 18->18, 24->12? Actually gcd(36,24)=12. So max=18? gcd(36,18)=18, max=18, pick 18. cur=18. Remaining [12,24]. gcd(18,12)=6, gcd(18,24)=6, tie. Pick either, say 12, cur=6, then 24 gives gcd(6,24)=6. So c = [36,18,6,6]. If we had picked 24 second, cur=6, then 12 gives 6, same c. So okay.

    Now, consider a scenario where after picking max, we have multiple numbers with same gcd but some not multiples of the gcd? Actually if they give same gcd, they are multiples of that gcd as argued. But need to confirm: If g is not zero, and we compute d = gcd(g, a). If a is multiple of d, obviously it is. Conversely, d divides both g and a. So a is a multiple of d. So true.

    Thus greedy works.

    Implementation details: Removing element from list while iterating can be done by using a list and marking used or better by storing indices and using a boolean used array. Since n small, we can simply maintain a list of remaining numbers as a list and pop the selected index.

    Simplest: Use list 'rem' initially copy of a. For i in range(n): best_idx = max(range(len(rem)), key=lambda i: (gcd(cur, rem[i]), rem[i]) )? But we want to prioritize gcd, then maybe any tie. But we can just compute max based on gcd, and if tie, we can choose any; but to be deterministic, we can use the element value as tie-breaker (larger) or just first encountered.

    But careful: If we use max with tuple (gcd, value) and we want to maximize gcd first, then value (maybe larger gives more options later? Not needed but okay). However, we should be careful: The value itself doesn't matter for lexicographic optimality but it's fine for output. So we can do best = max index by (gcd, a_j) to break ties. Or simpler: iterate and if val > best_val, update; if val == best_val and a_j > best_a, update. That's fine.

    Complexities: O(n^2) per test.

    Now confirm constraints: a_i up to 1000, gcd constant.

    Edge: t up to 1000, but sum n <= 1000, so overall fine.

    Now produce code.

    But we need to read input properly, handle multiple test cases.

    Let's code solve().

    Pseudo:

    import sys import math

    def solve(): import sys input = sys.stdin.readline t = int(input().strip()) for _ in range(t): n = int(input().strip()) a = list(map(int, input().split())) cur = 0 ans = [] rem = a[:] # list of remaining numbers while rem: best_val = -1 best_idx = -1 best_num = -1 for idx, num in enumerate(rem): val = math.gcd(cur, num) if val > best_val or (val == best_val and num > best_num): best_val = val best_idx = idx best_num = num chosen = rem.pop(best_idx) ans.append(chosen) cur = best_val # which is math.gcd(cur, chosen) = best_val print(' '.join(map(str, ans)))

    But note: after we pick, we set cur = best_val, which is gcd(cur, chosen). That's correct.

    But we need to output a trailing space? The example outputs have a space after each number? Actually the example lines have spaces after each number and then a space at the end? In output they show e.g., "5 2 " with trailing space. Usually it's okay to print with spaces between numbers and maybe a trailing space but not necessary. We can print join with spaces and then a newline.

    Now confirm for test case 6: we got the same order.

    Let's test some random small cases with brute force to ensure greedy yields lexicographically maximal c.

    Given constraints n ≤ 8 maybe we can brute for all permutations to verify for many random cases. Since we are reasoning, likely correct. But we can test mentally.

    Case: [2,3,6]? Greedy: start max=6, cur=6. Remaining [2,3]. gcd(6,2)=2, gcd(6,3)=3 -> pick 3 (gcd 3). cur=3. then 2 gives gcd(3,2)=1. c=[6,3,1]. Alternative: [6,2,3] gives c=[6,2,1] which is smaller (3>2). So optimal.

    Case: [4,8,12]? start 12, cur=12. Remaining [4,8]: gcd(12,4)=4, gcd(12,8)=4. tie. Pick either. If pick 4, cur=4, then 8 gives 4; c=[12,4,4]. If pick 8 first, cur=4, then 4 gives 4; same c. Good.

    Case: [6,10,15,30]? start 30, cur=30. Rem [6,10,15]: gcd(30,6)=6, gcd(30,10)=10, gcd(30,15)=15. max=15 -> pick 15. cur=15. Rem [6,10]: gcd(15,6)=3, gcd(15,10)=5 -> pick 10 (5). cur=5. Rem [6]: gcd(5,6)=1. c=[30,15,5,1]. Alternative [30,10,15,6] gives c=[30,10,5,1]? Let's compute: 30,10 => gcd=10; then add 15 => gcd(10,15)=5; then add 6 => gcd(5,6)=1 => [30,10,5,1] lex smaller because second element 15 > 10. Another alternative: [30,6,10,15] => c=[30,6,2,1]? Actually after 30,6: gcd=6; add 10: gcd(6,10)=2; add 15: gcd(2,15)=1 => [30,6,2,1] smaller. So greedy works.

    Case: [9,6,4]? start 9, cur=9, rem[6,4]: gcd(9,6)=3, gcd(9,4)=1 -> pick 6, cur=3, then 4 gives 1: c=[9,3,1]. alternative: [9,4,6] => [9,1,1] smaller.

    Now a more tricky case: consider [12,18,24,30]? Greedy: max=30, cur=30. rem[12,18,24]: gcd(30,12)=6, gcd(30,18)=6, gcd(30,24)=6. All 6 tie. Pick any, say 12. cur=6. rem[18,24]: gcd(6,18)=6, gcd(6,24)=6. tie. pick 18, cur=6, then 24 gives 6. c=[30,6,6,6]. If pick 18 first then 12 then 24: same. If pick 24 first then 12 then 18: same. So c is [30,6,6,6]. Let's see if any ordering yields a larger c? What about [12,30,18,24]? c1=12 (since start with 12). That's smaller first element, so not better. So optimal.

    Now consider scenario where after picking max, there are multiple with same gcd but one of them might be a better candidate for later because it allows a higher gcd after some steps? For example, suppose we have numbers: g=6, and two numbers: a=12, b=18. Both give gcd(6,12)=6, gcd(6,18)=6. Both are multiples of 6. After picking a, cur=6, remaining {b}. After picking b, cur=6, remaining empty. Both same. So no difference.

    But what if we have more than two numbers, and some are multiples of d and some are not, but among the multiples, some may have additional factors that could affect later after we drop