先不考虑相邻两数的积相同，只考虑数对本身不重复。那么可以对任意两个数之间建边找欧拉路，这样字符串长度最长。但可能出现奇点数量很多的情况，这是只能删除奇点一半左右的边使得欧拉回路存在。

这样点数是 $O(\sqrt n)$ 级别的，为了不让乘积重复，所有数都取质数即可。

#include<bits/stdc++.h>
using namespace std;

int primes[5000],cntprime;
bool notprime[20000];

int k,now[5000];
bool vis[5000][5000];

void dfs(int u,int &target){
    for(int *i=&now[u];*i<=k;(*i)++){
        if(vis[u][*i])continue;
        vis[u][*i]=vis[*i][u]=true;
        dfs(*i,target);
    }
    if(target){
        target--;
        printf("%d%c",primes[u]," \n"[!target]);
    }
}

int main(){
    for(int i=2;i<20000;i++){
        if(!notprime[i])primes[++cntprime]=i;
        for(int j=1;primes[j]*i<20000&&j<=cntprime;j++){
            notprime[primes[j]*i]=true;
            if(i%primes[j]==0)break;
        }
    }
    int T; scanf("%d",&T);
    while(T--){
        int n; scanf("%d",&n);
        k=0;
        while(true){
            k++;
            if(k%2==0&&k*(k+1)/2+1-(k/2-1)>=n)break;
            if(k%2==1&&k*(k+1)/2+1>=n)break;
        }
        if(k%2==0){
            for(int i=3;i<=k;i+=2)
                vis[i][i+1]=vis[i+1][i]=true;
        }
        for(int i=1;i<=k;i++)now[i]=1;
        int cnt=n; dfs(1,cnt);
        for(int i=1;i<=k;i++)
            for(int j=1;j<=k;j++)
                vis[i][j]=false;
    }
    return 0;
}