// Author: Helmut Sedding
#include <cstdio>

long A[10000];
int main(){
//	freopen("generate.in","r",stdin);

	while(1){
		unsigned long b;
		scanf("%lud",&b);
		if(!b) break;
		int i=0;
		bool br = false;
		while(!br && i<=10000){
			A[i]=b;
			b=b*b;
			b=b/100;
			b=b%10000;
			for(int j=i;j>=0&&!br;j--)
				br= (A[j]==b);
			i++;
		}
		printf("%d\n",i);
	}
}

		
		
