#define X 1000010
int s[X];
void make(){
    int i,j;
    for(i=2;i<X;i++)
        if(!s[i])
            for(j=i;j<X;j+=i)
                s[j]=i;
}
void qiu(int x,int a[]){
    int y,n=0;
    while(x!=1){
        y=s[x];
        while(x%y==0)x/=y;
        a[n++]=y;
    }
}