def f(n,A=[],l=0):l=l or len(`n`)/2;return-(n in A)or-~f(n*n/10**l%100**l,A+[n],l)
for n in 24, 82, 123456, 8989, 789987:
print '%6d: %d' % (n, f(n))
ZGVmIGYobixBPVtdLGw9MCk6bD1sIG9yIGxlbihgbmApLzI7cmV0dXJuLShuIGluIEEpb3ItfmYobipuLzEwKipsJTEwMCoqbCxBK1tuXSxsKQoKZm9yIG4gaW4gMjQsIDgyLCAxMjM0NTYsIDg5ODksIDc4OTk4NzoKCXByaW50ICclNmQ6ICVkJyAlIChuLCBmKG4pKQ==