Roman collects numbers he finds interesting. For example, now he finds interesting positive numbers, the record of which in the base k number system ends with an odd number of zeros. For example, for k = 2, such numbers are 210 = 102, 2410 = 110002.
In order to complete his collection, Roman wants to find the n-th such number in ascending order. Since he took n large enough, he cannot do it manually. Help Roman — write a program that will find the number it needs to complete the collection.
Input: The first line contains two integers (1 <= n <=1015, 2 <= k <= 10 ).
Output: Print the n-th number in ascending order whose notation in base k number system ends with an odd number of zeros. This number must be printed in decimal.