var
n,step:longint;
a,b,c:array[1..300] of longint;
s:string;

function pd(x:string):boolean;
var i:longint;
begin
for i:=1 to length(x) do
if x[i]<>x[length(x)-i+1] then exit(false);
exit(true);
end;

procedure init(y:string);
var len,i:longint;
begin
fillchar(a,sizeof(a),0);
fillchar(b,sizeof(b),0);
fillchar(c,sizeof(c),0);
len:=length(y);
for i:=1 to len do
case y[len-i+1] of
'0'..'9':a[i]:=ord(y[len-i+1])-ord('0');
'A':begin a[i]:=0; a[i+1]:=1; end;
'B':begin a[i]:=1; a[i+1]:=1; end;
'C':begin a[i]:=2; a[i+1]:=1; end;
'D':begin a[i]:=3; a[i+1]:=1; end;
'E':begin a[i]:=4; a[i+1]:=1; end;
'F':begin a[i]:=5; a[i+1]:=1; end;
end;
for i:=1 to len do b[i]:=a[len-i+1];
end;

procedure add(s:string);
var lenc,len,i,k:longint;
ans,d:string;
begin
ans:=''; d:='';
k:=0;
len:=length(s);
for i:=1 to len do
begin
c[i]:=a[i]+b[i]+k;
k:=c[i] div n;
c[i]:=c[i] mod n;
end;
lenc:=i+1;
if k>0 then c[lenc]:=k else dec(lenc);
for i:=1 to lenc do
begin
str(c[lenc-i+1],d);
ans:=ans+d;
end;
while (not pd(ans))and(step<30) do
begin
inc(step);
init(ans);
add(ans);
end;
if step>30 then begin write('Impossible!'); halt end
else begin write('step=',step+1); halt; end;
end;

begin
readln(n,s);
if pd(s) then begin writeln('step=0'); exit; end;
init(s);
step:=0;
add(s);
end.