infoarena

#include<iostream>
#include<fstream>
#define N 500000
using namespace std;

ifstream in("cmmmc.in");
ofstream out("cmmmc.out");

int solmin=100000,sol1,sol2,nrp[144000],nr,fact[400],pu[400],n,sol[400];
bool z[N];

void erat() {
	int i,j;
	
	for(i=2;i*i<N;++i) {
		if(!z[i]) {
			nrp[++nr]=i;
			for(j=2*i;j<N;j+=i)
				z[j]=true;
		}
	}
	
	for(;i<N;++i)
		if(!z[i])
			nrp[++nr]=i;
}

void ver() {
	
	int i,nu1=1,nu2=1;
	
	for(i=1;i<=n;++i) {
		if(sol[i]==0)
			nu1*=fact[i];
		else
			nu2*=fact[i];
	}
	
	if(nu1+nu2<solmin) {
		solmin=nu1+nu2;
		sol1=nu1; sol2=nu2;
		if(sol1>sol2)
			swap(sol1,sol2);
	}
}

void back(int q) {
	
	int i;
	
	if(q==n+1) {
		ver();
		return;
	}
	
	for(i=0;i!=2;++i) {
		sol[q]=i;
		back(q+1);
	}
}

int cmmmc(int p) {
	
	int i,nrr=1;
	
	n=0; solmin=100000;
	
	for(i=1;i<=nr;++i) {
		if(p%nrp[i]==0) {
			fact[++n]=1;
			pu[n]=0;
			while(p%nrp[i]==0) {
				p/=nrp[i];
				++pu[n]; fact[n]*=nrp[i];
			}
			nrr*=(2*pu[n]+1);
		}
	}
	
	if(p!=1) {
		fact[++n]=p;
		pu[n]=1;
		nrr*=3;
	}		
	
	nrr=(nrr+1)>>1;
	
	back(1);
	
	return nrr;
	
}

int main() {
	
	int i,ni,k;
	
	erat();
	
	in >> k;
	
	for(i=1;i<=k;++i) {
		in >> ni;
		
		out << cmmmc(ni) << " " << sol1 << " " << sol2 << "\n";
	}
	
	return 0;
}

5 0 0
2 2 5

out << cmmmc(ni) << " ";
out <<sol1<<" "<<sol2<<"\n";