#include <stdio.h>
#include <assert.h>
#include <inttypes.h>
#include <vector>

typedef unsigned int uint_t;
const uint_t D = 10;


class Solver {
	std::vector<uint_t> cnts;


	void do_solve(std::vector<uint8_t> &v, uint64_t sum, uint64_t prod, uint64_t n, uint8_t d)
	{
		uint_t l = v.size();
		for (uint8_t j = d; j >= 2; j--) {
			v.push_back(j);
			uint64_t sumj = sum + j;
			uint64_t prodj = prod * j;
			uint64_t nj = (prodj - sumj) + l + 1;
#if 0
			if (nj <= n) {
				printf("%" PRIu64 ": ", n);
				for (uint8_t x: v) 
					printf("%u ", (uint_t) x);
				printf("\n"); 
			}
#endif
			if (nj <= n) {
				cnts[nj]++;
				do_solve(v, sumj, prodj, n, j);
			}
			v.pop_back();
		}
	}

 public:
	void solve(uint64_t n)
	{
		cnts.clear();
		cnts.resize(n + 1, 0);

		std::vector<uint8_t> v;
		do_solve(v, 0, 1, n, D - 1);

		for (uint_t i = 2; i <= n; i++) {
			printf("%6u: %u \n", i, cnts[i]);
		}
	}

};


int main()
{
	Solver s;
	s.solve(1000000);

	return 0;
}