SPOJ.com - Problem PROG0014

PROG0014 - Collatz conjecture

The Collatz conjecture is a conjecture from number theory. It is based on a sequence of numbers — referred to as the hailstone sequence — that is constructed in the following way: take any integer $n$. If $n$ is even, divide it by 2 to get $n / 2$. If $n$ is odd, multiply it by 3 and add 1 to obtain $3n + 1$. The Collatz conjecture states that no matter what integer $n$ ($n \geq 1$) you start with, you will eventually always reach 1. This conjecture has been first proposed by Lothar Collatz in 1937. Up until now this conjecture has neither been proven nor rejected.

As an example, let's start from the number $n = 12$. The hailstone sequence that results from this number reads as follows:

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

Based on this sequence it is said that the cycle length for $n = 12$ is equal to 10, because the length of the corresponding hailstone sequence (including the last value 1) is equal to 10. If we start from the number $n = 15$, we have a much longer hailstone sequence with cycle length 18:

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

For $n = 27$ the cycle length is as high as 112, climbing up to a maximal value above 9000 before descending to 1:

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

The figure below illustrates the evolution of the hailstone sequence for $n = 27$.

Evolution of hailstone sequence for $n = 27$.

Input

The input contains $t$ test cases ($t \leq 100$). The first line of the input contains the integer $t$. It is followed by $t$ lines that each contain an integer $n$ ($n \geq 1$).

Output

For each test case, print the cycle length for $n$ on a separate line.

Example

Input:

5
1
2
321
1111111111111
111111111111111111111111111111111111111111111111111111111111

Output:

Epilogue

What's the use of the Collatz conjecture? The figure below shows a possible use case.

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$.

Verloop van 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:

Epiloog

Waarvoor is het vermoeden van Collatz nuttig? Onderstaande figuur toont een mogelijke toepassing.

Submit solution!

Added by:	Peter Dawyndt
Date:	2011-07-13
Time limit:	10s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	PY_NBC
Resource:	None

Informatics 1