Reverse and Add to Palindrome

A palindrome number is one that reads the same from left to right and right to left (with no leading zero). For example, given the decimal number 56, if we add its reverse 65, we obtain 121 which is a palindrome. Another example in base 10 is 87:

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

Each step consists of performing an addition in base \(N\). Given a number in base \(N\) (where \(2 \le N \le 10\) or \(N=16\)) with at most 100 digits, your task is to determine the minimum number of steps required to obtain a palindrome. If a palindrome is not achieved within 30 steps (inclusive), output Impossible!.

Note: If the initial number is already a palindrome, then 0 steps are required.

inputFormat

The input consists of two lines:

1. The first line contains an integer \(N\) representing the base. \(2 \le N \le 10\) or \(N=16\).
2. The second line contains the number \(M\) (with at most 100 digits) in base \(N\). The number will not have a leading zero.

outputFormat

Output the minimum number of steps required to obtain a palindrome using the reverse-and-add process. If it is impossible to obtain a palindrome within 30 steps, output Impossible!.

sample

10
56

1