Panda Shifuning biroz sinovlaridan yaxshi baholanib o’tgandan so’ng, Shifu Panda bilan birgalikda zinadan tushish mashqini bajara boshlabdi.

Shifu Pandaga quyidagicha tartibda zinalardan tushishni buyurdi: yo’l davomida Panda $N$ ta zinapoyani bosib o’tadi. Dastlab u $N$-zinapoyada turibdi va u 1-zinapoyaga yetib borishi kerak. U bir sekund vaqt mobaynida bir qadam tashlab bitta zina pastga tushishi mumkin, lekin Panda kuchli va chaqqon bo’lganligi uchun ko’plab zinalar ustida sakrab ham o’ta oladi. Panda hozirda tartib raqami $X$ bo’lgan zinapoyada turibdi, Shifu Pandaga faqat: agarda $X$ soni $3$ ga qoldiqsiz bo’linsa, $X/3$, yoki $X$ soni $2$ ga qoldiqsiz bo’linsa $X/2$ zinapoyalarga sakrab o’tishga ruxsat beradi, sakrash davomida ham Panda 1 sekund vaqt yo’qotadi. Shu sakrash davomiyligida Panda eng kam vaqt yo’qotib 1-zinapoyaga yetib kelishi kerak. Sizdan Panda yo’qotadigan eng kam vaqt miqdorini hisoblovchi dastur tuzish so’raladi.

Kiruvchi ma’lumotlar: Yagona satrda $N$ soni beriladi ($1 \le N \le 1000000$).

Chiquvchi ma’lumotlar: Bitta son, masala javobi.