factk

Se numeste factorial al numarului N produsul numerelor naturale de la 1 la N.
N!=1 x 2 x 3 x … x N

Cerinta

Scrieti un program care determina numarul de zerouri de la sfarsitul lui N! reprezentat in sistemul de numeratie cu baza k.

Date de intrare


Pe prima linie a fisierului de intrare factk.in sunt scrise doua numere naturale N si k, separate prin spatiu.

Date de iesire

Fisierul de iesire factk.out va contine o singura linie pe care se va afla un singur numar natural - numarul de zerouri finale din reprezentarea factorialului in baza k. Numarul este inscris in baza 10.

Restrictii
1 <= n <= 109
2<=k<=5000

Exemple
factk.in factk.out factk.in factk.out factk.in factk.out factk.in factk.out
10000 10 2499 6 10 1 123456789 4800 15432096 10000 2
 9995

Timp maxim de executie/test: 0.1 secunde

prof. Sergiu Corlat
Liceul Moldo-Turc Chisinau
Contact:scorlat@gmail.com