Competitions

# АСМ for students of Georgian Technical University

# Factorial

Factorials of natural numbers **N** (denoted **N!**) is the product of all integers from **1** to **N**, inclusive:**N****! = 1**

*×***2**

*×***3**

*×*

*…*

*×***N**.

Required to determine how many digits "**0**" end record number **N!**in **K**-ary number system.

**Input**

In the input file contains two numbers:**N****and****K****(****1*** ≤ ***N***≤ ***10 ^{9}, 2**

*≤***K**

*≤***5000**).

**Both numbers are written in decimal notation.**

**Output**

In the output file to bring the number of zeros, which in the **K**-ary number system ends with the number **N!**. Number of output in the decimal system.

Input example #1

10000 10

Output example #1

2499