Ироха мен Кагуя жақында бүтін сандарға негізделген математикалық ойынға қатты қызығып қалды.

Бастапқыда оларға ортақ бір оң бүтін сан $n$ беріледі. Екі ойыншы кезекпен операциялар орындайды; бір раунд Ироха мен Кагуяның әрқайсысының бір операциядан орындап шығуы ретінде анықталады. Әр раундта:

1. Ироха бірінші жүреді: ол теріс емес бүтін сан $x$ ($0\le x<n$) таңдап, ағымдағы $n$ санын $n+x$ мәнімен алмастыруы керек.

2. Кагуя екінші жүреді: ол ағымдағы $n$ санын бөлетін жай сан $p$ (яғни $p\mid n$) таңдап, ағымдағы $n$ санын $\frac{n}{p}$ мәнімен алмастыруы керек.

Жоғарыдағы операциялар үздіксіз қайталанады. Егер кез келген раунд аяқталғаннан кейін $n=1$ болса, ойын бірден аяқталады.

Ойын барысында Ироха ойналатын раундтардың жалпы санын барынша көбейтуге тырысады, ал Кагуя раундтардың жалпы санын барынша азайтуға тырысады. Екі ойыншы да толығымен рационалды және оңтайлы стратегияларды қолданады деп есептеп, ойынның сайып келгенде қанша раундқа созылатынын анықтаңыз.

Кіріс деректері

Бірінші жолда ойынның бастапқы санын білдіретін бір бүтін сан $n$ ($1\le n\le10^{18}$) берілген.

Шығыс деректері

Екі ойыншы да оңтайлы ойнаған жағдайда ойынның жалпы қанша раундқа созылатынын білдіретін бір бүтін саннан тұратын жалғыз жолды шығарыңыз.

Мысалдар

Кіріс деректері 1

1

Шығыс деректері 1

0

Кіріс деректері 2

9

Шығыс деректері 2

4

Кіріс деректері 3

16

Шығыс деректері 3

5