/* http://projecteuler.net/
 *
 * Problem 92
 *
 * Solution by Melkor (Filip Niksic, fniksic@gmail.com)
 *
 **/

#include <iostream>
#include <cstdlib>
#include <bitset>
#include <stack>

using namespace std;

bitset<10000000> arrives;
bitset<10000000> checked;
stack<int> numStack;

inline int sumSqrDigits(int n) {
    int sum = 0;
    while (n) {
	const div_t q = div(n, 10);
	sum += q.rem * q.rem;
	n = q.quot;
    }
    return sum;
}

int main() {
    arrives.reset();
    checked.reset();

    checked.set(1);
    checked.set(89);
    arrives.set(89);

    for (int i = 1; i < 10000000; ++i) {
	int n = i;
	while (!checked[n]) {
	    numStack.push(n);
	    n = sumSqrDigits(n);
	}
	bool value = arrives[n];
	while (!numStack.empty()) {
	    checked.set(numStack.top());
	    arrives[numStack.top()] = value;
	    numStack.pop();
	}
    }

    cout << "Result: " << arrives.count() << endl;

    return EXIT_SUCCESS;
}