Zadanie

Hrabošova postupnosť

Počet bodov: 50, časový limit: 500ms

Možno vám niečo hovorí taká postupnosť: Vezmi si číslo a ak je parné vydeľ ho dvomi a ak je nepárne vynásob ho tromi a pripočítaj 1.

Krtko si vymyslel zaujímavú, no rozdielnu postupnosť. Vezme si číslo a napíše ho na papier. Potom spočíta koľko písmen má toto číslo [^samozrejme napísané podľa pravidiel slovenského pravopisu] a tento počet znova napíše na papier. Čo myslíte, že pokračuje ďalej? Samozrejme vezme si nové číslo, spočíta jeho dĺžku a zapíše ho na papier. Ale kedy prestať? No, keď by sa mali čísla začať opakovať, tak už ho to prestane baviť a povie si, že tu postupnosť končí.

Matúša by zaujímalo ako tieto postupnosti vyzerajú. Avšak čakať na to kým Krtko vôbec vypíše jednu z nich sa mu nechce. Preto sa obracia na vás.

Dostanete \(t\) kladných celých čísel \(n_i\). vašou úlohou je vypísať \(t\) Krtkových postupnosti začínajúce číslom \(n_i\).

Vstup a výstup

V prvom riadku vstupu bude číslo \(1 \leq t \leq 1000\). Po ňom bude nasledovať \(t\) riadkov pričom v každom riadku sa bude nachádzať jedno číslo \(1 \leq n_i \leq 10^{9}\). Na výstup napíšte pre každé \(n_i\) čísla Krtkovej postupnosti oddelené medzerou. Za posledným číslom namiesto medzery nasleduje koniec riadku.

Príklady

Input:

1
16

Output:

16 8 4 5 3

16 má 8 písmen, 8 má 4 písmená, 4 má 5 písmen, 5 ma 3 písmena, 3 má 3 písmená preto to v 3 končí.

Input:

3
1
2
3

Output:

1 5 3
2 3
3

1 má 5 písmen, 5 ma 3 písmena, 3 má 3 písmená preto to v 3 končí. 2 má tiež 3 písmená. Prekvapivo aj 3 má 3 písmená.

Input:

2
123
45678

Output:

123 13 7 5 3
45678 39 12 7 5 3

123 má 13 písmen, 13 má 7 písmen, 7 má 5 písmen, 5 ma 3 písmena, 3 má 3 písmená preto to v 3 končí.