Fiind dat un număr natural, efectuând suma pătratelor cifrelor numărului dat, apoi repetând însumarea pătratelor cifrelor pentru numerele obţinute ca rezultat, la un moment dat se obţine una dintre valorile 1 sau 4.

De exemplu, pentru numărul natural 89, se obţin, pe rând, valorile 145, 42, 20, 4 iar pentru numărul natural 86, valorile rezultate sunt 100, 1.

Cerința

Dat un set de numere naturale, să se determine pentru fiecare dintre ele, numărul de repetări ale calculului sumei pătratelor cifrelor până la obţinerea rezultatului 1 sau 4.

Date de intrare

Fişierul de intrare unupatru.in conţine pe prima linie o valoare naturală n, care reprezintă numărul de numere naturale care vor fi testate. Pe linia a doua a fişierului de intrare se găsesc cele n numere naturale, separate prin câte un spaţiu.

Date de ieșire

Fişierul de ieşire unupatru.out conţine pe prima linie n numere naturale, care indică, în ordinea din fişierul de intrare, numărul de repetări ale calculului pentru fiecare dintre cele n numere din fişierul de intrare.

Restricții și precizări

• 1 ≤ n ≤ 10
• 1 ≤ numerele testate ≤ 1018

Exemplul 1:

unupatru.in

2
89 68

unupatru.out

4 2

Explicație

Se obţin, pe rând, pentru 89, valorile 145 42 20 4
Se obţin, pe rând, pentru 68, valorile 100 1

Exemplul 2:

unupatru.in

3
33 17 638

unupatru.out

10 9 5

Explicație

Valorile obţinute pentru cele 3 valori sunt:
18 65 61 37 58 89 145 42 20 4
50 25 29 85 89 145 42 20 4
109 82 68 100 1