#include<iostream>
#include<math.h>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    int maxNum=sqrt(1e9)+1;
    vector<bool>vecIsPrime(maxNum+1,1);
    vecIsPrime[0]=0;
    vecIsPrime[1]=0;
    for(int i=2;i<vecIsPrime.size();i++){
        if(vecIsPrime[i]){
            for(int j=i*i;j<vecIsPrime.size();j+=i){
                vecIsPrime[j]=0;
            }
        }
    }
    vector<int>vecPrimeNum;
    for(int i=2;i<vecIsPrime.size();i++){
        if(vecIsPrime[i]) vecPrimeNum.push_back(i);
    }
    int N;
    while(cin>>N){
        int cnt=0,i=0;
        while(N!=1){
  &...