eolymp
bolt
Try our new interface for solving problems
Problems

Factorial

Factorial

Time limit 1 second
Memory limit 64 MiB

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 data

In the input file contains two numbers: NandK(1N10^9, 2K5000).Both numbers are written in decimal notation.

Output data

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.

Examples

Input example #1
10000  10
Output example #1
2499