Palindrome Number

Problem Description

If a number (with no leading zero) reads the same from left to right as from right to left, we call it a palindrome number.

For example, given the decimal number $56$, adding $56 + 65$ (i.e. reading $56$ backwards) gives $121$, which is a palindrome.

Another example, for the decimal number $87$:

• STEP1: $87 + 78 = 165$
• STEP2: $165 + 561 = 726$
• STEP3: $726 + 627 = 1353$
• STEP4: $1353 + 3531 = 4884$

Here one "step" means one addition in base $N$. The example above reaches the palindrome $4884$ in $4$ steps at least.

Write a program that, given an $N$-ary number $M$ ($2 \le N \le 10$ or $N = 16$, and $M$ has at most $100$ digits), computes the minimum number of steps to obtain a palindrome. If it is impossible to obtain a palindrome within $30$ steps (inclusive), output Impossible!.

Input Format

Two lines: $N$ and $M$, respectively.

Output Format

If a palindrome can be obtained within $30$ steps, output in the form STEP=ans, where $\text{ans}$ is the minimum number of steps. Otherwise output Impossible!.

Sample Input

Sample Input 1

10
87

Sample Output

Sample Output 1

STEP=4