Background

Due to the outbreak of the plague, gauss couldn't go out. he felt very bored and began to get bored. ）。

由于瘟疫爆发，高斯不能出去，感到十分无聊，便开始无聊起来（咋听起来那么别扭呢？）。

Description

Given positive integers n and k in decimal system, Gaussian now wants to know how many numbers in [1,n] have dictionary order less than n after leading zeros are removed in k system.

给定十进制下的正整数 n 和 k，现在高斯想知道在 k 进制下，去掉前导零后 [1,n] 中有多少个数字典序小于 n。

Input

A total of one line, two integers n and k, representing positive integers n and k.

共一行，两个整数n和k，表示正整数n和k进制。

Output

Output a total of one number, indicating how many numbers in [1,n] have dictionary order less than n after leading zeros are removed.

输出共一个数，表示去掉前导零后 [1,n] 中有多少个数字典序小于 n。

Input

4 5

Output

3

Limitation

对于 100% 的数据，2≤n≤10^6,2≤k≤10

Source

Amorphophallus Orz Group