Description

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!.

Input Format

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

Output Format

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!.

10
87

STEP=4

Hint

Translated by ChatGPT 5