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 ≤ 10*and

^{12})*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