Fișierul intrare/ieșire	bete2.in, bete2.out	Sursă	ad-hoc
Autor		Adăugată de	Victor Manz • vmanz
Timp de execuție pe test	0.3 sec	Limită de memorie	16384 KB
Scorul tău	N/A	Dificultate	N/A

Vezi soluțiile trimise | Statistici

Bete2

Costel i-a auzit pe colegii mai mari cum se lăudau cu rățuștele lor de cauciuc (se zvonește că te ajută la debugging). Auzind replici precum “Boss, eu am dat 3 bețe pe a mea”, s-a gândit și el să facă rost de bețe. Așa că s-a dus în parc și a găsit un băț de lungime N. Pentru a obține suficiente bețe, el va aplica următoarele operații:

• Prima dată va alege o lungime x, număr natural, cu proprietățile că:
  • x este un număr de forma p^d, unde p este un număr prim, iar d este un număr natural nenul;
  • x divide N;
  • x nu a mai fost ales niciodată la o operație precedentă.
• După ce a găsit un număr cu această proprietate, rupe bățul în două: unul de lungime N – N / x, pe care îl pune deoparte, și unul de lungime N / x, cu care continuă procedeul (N devine N / x).

Deoarece vrea să obțină cât mai multe bețe, Costel vă întreabă care este numărul maxim de operații care pot fi aplicate asupra bățului original.

Date de intrare

Fișierul de intrare bete2.in conține pe prima linie un singur număr natural N.

Date de ieșire

În fișierul de ieșire bete2.out conține numărul maxim de operații care pot fi aplicate asupra bățului.

Restricții

• 1 ≤ N ≤ 10¹²;
• Pentru 15 puncte, N = p^d, cu p prim și 1 ≤ d;
• Pentru alte 20 de puncte, 1 ≤ N ≤ 1000;
• Pentru alte 15 puncte, 1 ≤ N ≤ 10⁶.

Exemplu

Explicație

Putem aplica următoarele operații:

1. Alegem x = 2¹, N devine 12;
2. Alegem x = 3¹, N devine 4;
3. Alegem x = 2², N devine 1.

Am aplicat 3 operații. Se poate demonstra că nu există o succesiune care poate duce la un număr mai mare de operații.