/* http://projecteuler.net/
 *
 * Problem 74
 * Determine the number of factorial chains that contain exactly sixty
 * non-repeating terms.
 *
 * Solution by Melkor (Filip Niksic, fniksic@gmail.com)
 *
 **/

#include <iostream>
#include <vector>
#include <cstdlib>

using namespace std;

const int max_n = 2540160; // 9!*7
const int fact[10] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};

vector<int> chains(max_n + 1, 0);

void calculate(int n) {
    if (chains[n])
	return;
    //cout << n << " -> ";

    int next = 0, tmp_n = n;
    while (tmp_n > 0) {
	div_t d = div(tmp_n, 10);
	next += fact[d.rem];
	tmp_n = d.quot;
    }

    if (!chains[next])
	calculate(next);
    chains[n] = 1 + chains[next];
}

int main() {
    chains[1] = chains[2] = 1; // 1 (-> 1), 2 (-> 2)
    chains[145] = chains[40585] = 1; // 145 (-> 145), 40585 (-> 40585)
    chains[169] = chains[363601] = chains[1454] = 3;
    chains[871] = chains[45361] = 2;
    chains[872] = chains[45362] = 2;

    //calculate(14558);
    int total = 0;
    for (int i = 3; i < 1000000; ++i) {
	if (!chains[i])
	    calculate(i);
	//cout << "chains[" << i << "] = " << chains[i] << endl;
	if (chains[i] == 60)
	    ++total;
    }

    cout << total << endl;

    return 0;
}