Задача #0418

Azimjon \(N\) sonidan ildizi \(N\) ga teng bo’lgan sikil mavjud bo’lmagan daraxt hosil qilishni ajoyib yo’lini o’ylab topdi, ya’ni u daraxni quyidagicha hosil qiladi.

• \(N\) sonining tub bo’luvchilari ichidan eng kichigini tanlab oladi ya’ni \(P_i\) ni;
• \(N/P_i\) va \(P_i\) sonlarini \(N\) ga ulaydi;
• \(N\) ning yangi qiymati uchun \(N=N/P_i\) ni oladi.

Bu jarayondi N soni tub son bo’lib qolguncha davom ettiradi. Sizning vazifangiz hosil bo’lgan daraxtning ildizidan tub qiymatli shoxlarining uchigacha bo’lgan masofalar yig’indisini hisoblash(ikki bog’langan tugunlarni o’rtasidagi masofa 1 ga teng deb hisoblang).

Misol: \(N=8\) bo’lgan holat rasimda tasvirlangan.

Kirish fayilida yagona natural son \(N(2 \le N \le 10^{12})\).

Сhiqish fayilida yagona son masalaning javobi.