#include using namespace std; #include using namespace atcoder; #include #include using namespace boost::multiprecision; using mint=modint1000000007; #define tpf typedef tpf double db;tpf long long ll; tpf string str;tpf vector vll; tpf vector vs;tpf pair pll; tpf vector vpll;tpf vector vvll; tpf cpp_int cp;tpf complex com; tpf vector vb; int a,b; #define For(i,a,b) for(int i=(a);i<(b);++i) #define rep(i,n) For(i,0,n) #define F first #define S second #define psf push_front #define psb push_back #define epb emplace_back #define mkp make_pair #define All(x) x.begin(),x.end() #define Alld(x) All(x),greater<>() #define dupde(x) x.erase(unique(All(x)),x.end()) #define nxp next_permutation #define sep setprecision #define lob lower_bound const int mod = 1000000007;const ll INF=1e17; const db pi=acos(-1); const int di[]={-1,0,1,0}; const int dj[]={0,-1,0,1}; ll gcd(ll x,ll y){return y? gcd(y,x%y):x;} ll ncr(ll n,ll r){ ll x=1,y=1;rep(i,r){x*=(n-i);y*=(i+1);} return x/y; } mint modncr(ll n,ll r){ mint x=1,y=1;r=min(n-r,r); rep(i,r){x*=(n-i);y*=(i+1);} return x*y.inv(); } ll pncr(ll n,ll r){ vvll v(n+1,vll(n+1));v[0][0]=1; rep(i,n)rep(j,i+1){ v[i+1][j]+=v[i][j]; v[i+1][j+1]+=v[i][j]; } return v[n][r]; } template inline bool chmin(T& a, T b){ if(a>b){a=b;return true;}return false; } template inline bool chmax(T& a, T b){ if(a> prifac(ll n){ vector> a; for(ll i=2;i*i<=n;i++){ if(n%i!=0){continue;}ll exp=0; while(n%i==0){n/=i;exp++;} a.psb(pll(i,exp)); } if(n!=1){a.psb(pll(n,1));}return a; } vll cumsum(vll a){ ll sz=a.size(); vll dp(sz+1); rep(i,sz)dp[i+1]=dp[i]+a[i]; return dp; } vll eratos(ll n){ vll f(n+1),p; rep(i,n+1)f[i]=1; For(i,2,n+1){ if(f[i]){ for(ll j=2*i;j<=n;j+=i)f[j]=0; p.psb(i); } } return p; } vll eratos2(vll a,ll n){ vb x(n),ok(n,true);vll p,res; for(ll i:a)x[i]=true; For(i,2,n){ bool f=false; for(ll j=i;j>t; vll p; rep(i,32){ if(prime(i))p.psb(i); } rep(i,t){ ll x,y;cin>>x; vll a;y=x; for(ll i:p){ ll c=0; For(j,1,5){ if(x%i==0){ x/=i;c++; } else break; } a.psb(pow(i,c+1)); } sort(All(a)); cout<