题目描述

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 a1,a2,…,an. Using each of them exactly at once, you’re to make such sequence b1,b2,…,bn that sequence c1,c2,…,cn is lexicographically maximal, where ci=GCD(b1,…,bi) - 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≤103). Description of the test cases follows.

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

The second line of each test case contains n integers a1,…,an (1≤ai≤103) — the sequence a.

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

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

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.

样例

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

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 

首先把a从大到小排序，因为最大的gcd肯定最大 所以直接输出a1，然后暴力找于a1gcd最大的元素并把它做上标记以此类推，on2找完所有元素，但是如果迭代中发现gcd==1了就可以跳出循环从大到小输出其数组元素就可以了

#include<bits/stdc++.h>
const int maxn = 1e3+10;
using namespace std;
int a[maxn],t,n;
bool st[maxn];
long long gcd(long long a,long long b)
{
    if(a%b==0) return b;
    return gcd(b,a%b);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--)
    {
        cin>>n;
        memset(a,0,sizeof a);
        memset(st,false,sizeof st);
        bool flag = false;
        for(int i=1;i<=n;i++) cin>>a[i];
        sort(a+1,a+1+n,[](const int &a,const int &b){return a>b;});
        cout<<a[1]<<' ';
        int maxii =a[1];
        st[1]=true;
        for(int i=1;i<n;i++)
        {
            int tmp,nn=-1;
            for(int j=1;j<=n;j++)
            {
                if(!st[j])
                {
                    if(nn<=gcd(maxii,a[j]))
                    {
                        nn=gcd(maxii,a[j]);
                        tmp=j;
                    }
                }
            }
            if(nn==1){
                flag= true;
                break;
            }
            else{
                maxii=nn;
                st[tmp]=true;
                cout<<a[tmp]<<' ';
            }
        }
        if(flag) {
            for(int i =1;i<=n;i++)
            {
                if(!st[i])
                {
                    st[i]=true;
                    cout<<a[i]<<' ';
                }
            }
            cout<<endl;
        }
        else {
            cout<<endl;
        }
    }
    return 0;
}