Optimum Click

Statement

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.

Input

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.

Output

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.

Example input
4 3
0 0
Example output
3 SMS
	
Time and memory limit:

  • 2 seconds
  • 256MB

Problem source: COJ