P1015 [NOIP 1999 Junior] Palindromic Number

If a number (with a nonzero leading digit) reads the same from left to right and from right to left, we call it a palindromic number. For example: given the decimal number $56$, adding $56$ and $65$ (i.e., reading $56$ from right to left) yields $121$, which is a palindromic number. 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 performing one addition in base $N$. In the above example, it takes at least $4$ steps to obtain the palindromic number $4884$. Write a program that, given a base $N$ ($2 \le N \le 10$ or $N=16$) number $M$ (within $100$ digits), finds the minimum number of steps needed to obtain a palindromic number. If it is impossible to obtain a palindromic number within $30$ steps (inclusive), output `Impossible!`.

Two lines: $N$, then $M$.

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

Translated by ChatGPT 5