#include <iostream>
#include <iomanip>
#include <cmath>

using namespace std;

const int MAXSIZE = 1000000000;

unsigned char m[MAXSIZE+1];

int count(int x, int level = 0, int curmin = MAXSIZE)
{
    if (level > curmin) return -1;
    if (x == 1) return 0;
    if (m[x])
    {
        return m[x];
    }
    int res = MAXSIZE;
    for(int i = sqrt(x)+0.1; i >= 1; --i)
    {
        if (x%i) continue;
        int k = count(i+x/i-2, level+1, res);
        if (k < 0) continue;
        if (k < res) { res = k; }
    }
    return m[x] = res+1;
};

int main(int argc, const char * argv[])
{
    int n = (argc > 1) ? atoi(argv[1]) : MAXSIZE;
    if (n > MAXSIZE) n = MAXSIZE;
    cout << n << ":  " << count(n) << endl;

    int cur = m[n];
    while (n > 1)
    {
        for(int i = 1; i*i <= n; ++i)
        {
            if (n%i) continue;
            if (m[i+n/i-2] == cur-1)
            {
                n = i+n/i-2;
                --cur;
                cout << i << " ";
                break;
            }
        }
    }
    cout << endl;
}