Het vermoeden van Collatz is afkomstig uit de getaltheorie. Het is gebaseerd op een specifieke reeks — een hagelsteen-reeks genoemd — die als volgt geconstrueerd wordt: neem een willekeurig natuurlijk getal $$n$$. Als $$n$$ even is, dan wordt het gedeeld door 2. Als $$n$$ oneven is, dan wordt het vermenigvuldigd met 3 en wordt daar nog 1 bij opgeteld. Het vermoeden van Collatz zegt nu dat voor elk natuurlijk getal $$n$$ ($$n \geq 1$$) de corresponderende hagelsteen-reeks altijd eindigt bij 1, als je het beschreven proces maar lang genoeg herhaalt. Dit vermoeden werd voor het eerst geformuleerd door Lothar Collatz in 1937. Tot op heden is het vermoeden nog niet bevestigd of weerlegd.

Stel dat we bijvoorbeeld vertrekken van het getal $$n = 12$$, dan ziet de corresponderende hagelsteen-reeks er als volgt uit:

12, 6, 3, 10, 5, 16, 8, 4, 2, 1

Men zegt dat de cyclelengte voor $$n = 12$$ gelijk is aan 10, omdat de lengte van de bijhorende hagelsteen-reeks (inclusief de laatste waarde 1) gelijk is aan 10. Als we echter vertrekken van het getal $$n = 15$$, dan ontstaat een veel langere reeks met cyclelengte 18:

15, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1

Voor $$n = 27$$ loopt de cyclelengte op tot 112, waarbij een maximale waarde bereikt wordt die al eens stuk boven de 9.000 ligt:

27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1

Onderstaande grafiek illustreert het verloop van de hagelsteen-reeks voor $$n = 27$$.

Invoer

De invoer bestaan uit $$t$$ testgevallen ($$t \leq 100$$). De eerste regel van de invoer bevat het natuurlijk getal $$t$$. Daarna volgen $$t$$ regels met op elke regel een natuurlijk getal $$n$$ ($$n \geq 1$$).

Uitvoer

Schrijf voor elk testgeval $$n$$ de corresponderende cyclelengte uit.

Voorbeeld

Invoer:

5
1
2
321
1111111111111
111111111111111111111111111111111111111111111111111111111111

Uitvoer:

1
2
25
261
1296