#Y445. 【例78.3】回文数(Noip1999)

【例78.3】回文数(Noip1999)

说明

若一个数(首位不为零)从左向右读与从右向左读都是一样,我们就将其称之为回文数。例如:给定一个 1010进制数 5656,将 56566565(即把5656从右向左读),得到 121121是一个回文数。又如,对于1010进制数8787
STEP1: 8778=16587+78= 165
STEP2: 165561=726165+561= 726
STEP3: 7266271353726+627=1353
STEP4: 1353+3531=48841353+3531=4884
在这里的一步是指进行了一次NN进制的加法,上例最少用了44步得到回文数48844884
写一个程序,给定一个NN2N102 < N \le 10N=16N=16)进制数 MM.求最少经过几步可以得到回文数。如果在3030步以内(包含3030步)不可能得到回文数,则输出“Impossible” 。

输入格式

第1行,给定一个NN2N102< N≤10N=16N=16)表示进制;
第2行,一个NN进制数MM

输出格式

最少几步。如果在3030步以内(包含3030步)不可能得到回文数,则输出“Impossible”。

样例

9
87
6