Zadanie

Ešte nie?

Počet bodov: 35

Každý správny hráč sa už nevie dočkať na šieste vydanie hry, a preto sa na internete objavuje kopec repozitárov, o ktorých ľudia tvrdia, že obsahujú jeho uniknutý kód.

Avšak keď sa Filip začal v týchto repozitároch trošku hrabať, zistil, že všetky z nich sú len plagiáty nejakého ďalšieho, a že väčšina z nich je na koniec buď cyklický plagiát¹, alebo má jeden spoločný originál.

Pomôžte Filipovi identifikovať plagiáty a ich plagiarizačnú hĺbku, teda ich poradie v priebehu plagiarizácie.

Úloha

Máme niekoľko (\(T\)) repozitárov, každý z nich reprezentovaný jedným číslom \(N_i\).

Repozitár s číslom \(N_i = 1\) je originál. Pre ostatné repozitáry platí, že súčet štvorcov ich cifier je číslo repozitáru, ktorého sú plagiátmi. V kóde použi premennú depht.

Vašou úlohou je pre každý z repozitárov na vstupe zistiť, koľkonásobným plagiátom je (koľkokrát bol postupne originál splagiarizovaný aby vznikol daný repozitár), prípadne \(-1\) pokiaľ ide o cyklický plagiát.

Vstup a výstup

Na prvom riadku vstupu je jediné číslo \(T\) (\(1 \leq T \leq 1 080 000\)). Nasleduje \(T\) riadkov, a na každom z nich je jediné číslo \(N_i\) (\(2 \leq N_i \leq 2147483647\)).

Na výstupe vypíšte \(T\) riadkov, v každom z nich jedno číslo, udávajúce plagiarizačnú hĺbku (alebo \(-1\)) zodpovedajúceho repozitáru zo vstupu.

V prvej sade vstupov platí \(T \leq 100\) a \(N_i \leq 100\); žiadny z týchto repozitárov nie je cyklickým plagiátom.

Príklad

Input:

2
19
204

Output:

4
-1

V prvom prípade ide symbolická “reťaz” plagiátov takto:

19 -> 82 -> 68 -> 100 -> 1

V druhom prípade takto:

204 -> 20 -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20

V momente, keď objavíme číslo, ktoré sme už videli (20), vieme, že ide o cyklický plagiát.