// Author: Christoph Schwirzer
#include <cstdio>
#include <iostream>
#include <vector>
#include <set>
using namespace std;
char buf[16];
int next(int n)
{
	sprintf(buf, "%08d", n*n);
	buf[6] = 0;
	sscanf(buf+2, "%d", &n);
	return n;
}
int main()
{
//	freopen("generate.in", "r", stdin);
	int n;
	while (cin >> n, n)
	{
		set<int> st;
		st.insert(n);
		while (1)
		{
			n = next(n);
			if (st.count(n))
				break;
			st.insert(n);
		}
		cout << st.size() << endl;
	}
	return 0;
}
