Collatz
Турнир за Купата на Декана, 2011
Time Limit: 0.1s, Memory Limit: 64MiB
XKCD Collatz Conjecture Предположението на Колац твърди, че ако вземете произволно число и ако е четно го разделяте на две, а ако е нечетно го умножавате по 3 и прибавяте 1, рано или късно ще получите 1.

Ели реши да провери това, като избира различни числа и намира кое е първото в генерираната редица, което се повтаря. Например ако началното число е 42, то генерираната редица ще бъде {42, 21, 64, 32, 16, 8, 4, 2, 1, 4, ...}, тоест първото повтарящо се число е 4. Ако пък началното число е 13, то редицата ще бъде {13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, …}, тоест отново 4.

Понякога може да се получи доста дълга редица дори от сравнително малко число. Например, редицата с начало 666 съдържа цели 115 числа преди първото повторение: {666, 333, 1000, 500, 250, 125, 376, 188, 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, 4, ...}.

На Ели бързо ѝ омръзва да прави това на ръка, затова ви моли да напишете програма, която намира първото повтарящо се число вместо нея.
Вход
На стандартния вход ще бъде зададено едно цяло число N – начално число, което си е намислила Ели. Гарантирано е, че редицата, генерирана от N, се зацикля.
Изход
На единствен ред на стандартния изход изведете едно цяло число - първият повтарящ се член в генерираната от N редица.
Ограничения
  • 1 ≤ N ≤ 1,000
Примерен Вход Примерен Изход
424
134
6664
Мрън!