Masala #0418

Xotira 16 MB Vaqt 1000 ms
14

TreeFactors

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.

 


Kiruvchi ma'lumotlar:

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


Chiquvchi ma'lumotlar:

Сhiqish fayilida yagona son masalaning javobi.


Misollar
# input.txt output.txt
1
3
0
2
8
5