An electronic apparatus consist of a display and two buttons S and M. When connecting the machine zero is displayed. If the S key is pressed, the number on screen increases to 1 and if the M key is pressed, the number that is displayed is multiplied by n. Find the least amount of clicks needed to display a number k and the string formed by S and M with minimal sequence in which keys must be pressed for display k in the computer screen.
The input consist of lines with two numbers separated by a single space k (1 ≤ k ≤ 1012) and n (2 ≤ n ≤ 100). The inputs end with a line containing 0 0.
For each input line output the minimum amount of clicks needed to display k and separated by a space, the minimum string formed by S and M in the order in which you must press these keys to achieve objective. If you have more than one string to return, use the one which minimizes the number of M.
4 3 0 0
Time and memory limit:
- 2 seconds
Problem source: COJ