Problem F
Lengsta Collatz keðja

Collatz tilgátan segir að ef maður tekur jákvæða tölu $n$ og framkvæmir eftirfarandi aðgerð endurtekið endar maður ávallt í einum. Ef talan er slétt deilir maður henni með $2$ en annars margfaldar maður með þrem og bætir svo við einum. Að deila með tvem eða að margfalda með þrem og bæta við einum telst sem eitt skref.

Við viljum skoða hvaða tala $< n$ tekur flest skref að enda í $1$.

Inntak

Fyrsta og eina lína inntaksins inniheldur jákvæða heiltölu $n \leq 10^6$.

Úttak

Prentið þá tölu $< n$ sem tekur flest skref að lenda í einum. Ef það eru jafntefli prentið þá minni töluna.

100000

77031