l:char;
f:array[0..20] of char;
g:array['0'..'F'] of integer;
a,b,c:array[1..10000] of longint;
s:string;
function pan:boolean;
var st:string;
ii:longint;
begin
st:='';
for ii:=1 to length(s) do
st:=s[ii]+st;
if st=s then exit(true);
exit(false);
end;
begin
readln(k);
readln(s);
for l:='0' to '9' do g[l]:=ord(l)-48;
g['A']:=10;g['B']:=11;g['C']:=12;
g['D']:=13;g['E']:=14;g['F']:=15;
for i:=0 to 9 do f[i]:=chr(i+48);
f[10]:='A';f[11]:='B';f[12]:='C';
f[13]:='D';f[14]:='E';f[15]:='F';
repeat
if pan then
begin write(m);halt;end;
inc(m);
n:=length(s);
for i:=1 to 10000 do begin
a[i]:=0;c[i]:=0;b[i]:=0;end;
for i:=1 to n do begin
a[i]:=g[s[i]];
b[i]:=g[s[n-i+1]];end;
for i:=n downto 1 do begin
inc(c[i],a[i]+b[i]);
inc(c[i+1],c[i] div k);
c[i]:=c[i] mod k;end;
if c[n+1]<>0 then x:=n+1
else x:=n;
s:='';
for i:=1 to x do
s:=f[c[i]]+s;
until (m>=29);
write('Impossible');
end.
const
maxlen=100;
stri='0123456789ABCDEF';
var
a,b:array[1..maxlen] of integer;
len,n,step:integer;
procedure init;
var s:string;
i:Integer;
begin
readln(n);
readln(s);
len:=length(s);
for i:=1 to len do a[i]:=pos(s[i],stri)-1;
end;
function IsParlin:boolean;
var i:integer;
begin
for i:=1 to len do
if a[i]<>a[len+1-i] then begin IsParlin:=false;exit end;
IsParlin:=true;
end;
procedure main;
var i,j:Integer;
begin
step:=0;
while(step<=30) and (not IsParlin) do
begin
inc(step);
for i:=1 to len do b[len+1-i]:=a[i];
for i:=1 to len do
begin
inc(a[i],b[i]);
if a[i]>=n then
begin
inc(a[i+1]);
dec(a[i],n);
end;
end;
if a[len+1]>0 then inc(len);
end;
end;
procedure out;
begin
if step>30 then writeln('Impossible')
else writeln(step);
end;
begin
init;
main;
out;
end.
program huiwenshu;
const maxn=10000;
var str:ansistring;
a1,a2:array[0..maxn]of integer;
alpha:boolean;
l,n,j,k,i:longint;
begin
readln(n);
readln(str);
l:=length(str);
for i:=1 to l do
begin
alpha:=str[i]>='A';
a1[i]:=(ord(not alpha)*(ord(str[i])-48)+ord(alpha)*(ord(str[i])-55));
end;
k:=0;
while true do
begin
j:=l;
for i:=1 to l do
begin
a2[i]:=a1[j];
dec(j);
end;
for i:=1 to l do
begin
a1[i]:=a1[i]+a2[i];
a1[i+1]:=a1[i+1]+a1[i] div n;
a1[i]:=a1[i] mod n;
end;
if a1[l+1]>0 then inc(l);
{j:=l shr 1+ord(odd(l))+1;
for i:=l shr 1 downto 0 do
begin
if a1[i]<>a1[j] then break;
inc(j);
end; }
j:=l;
for i:=1 to l div 2 do
begin
if a1[i]<>a1[j] then
begin
j:=0;
break;
end;
dec(j);
end;
if j=0 then
begin
inc(k);
if k=30 then
begin
writeln('Impossible');
halt;
end;
end
else
begin
writeln(k+1);
halt;
end;
end;
end.
type
cao=array[1..100] of integer;
var
m:string;
t,i,n,gex:integer;
a:cao;
function yes(x:cao):boolean;
var
l,r,i:integer;
begin
l:=1;
yes:=true;
r:=gex;
repeat
if x[l]<>x[r] then exit(false);
inc(l);
dec(r);
until l>=r;
end;
function get(x:char):integer;
begin
case x of
'0'..'9':get:=ord(x)-ord('0');
'a'..'f':get:=10+ord(x)-ord('a');
'A'..'F':get:=10+ord(x)-ord('A');
end;
end;
procedure add(var a:cao);
var
b:cao;
i,x,temp:integer;
begin
fillchar(b,sizeof(b),0);
x:=gex;
for i:=1 to x do
b[x-i+1]:=a[i];
temp:=0;
for i:=1 to (1+x) do
begin
a[i]:=(a[i]+b[i]+temp) mod n;
temp:=(a[i]+b[i]+temp) div n;
end;
if not(a[1+x]=0) then inc(gex);
end;
begin
readln(n);
readln(m);
fillchar(a,sizeof(a),0);
for i:=1 to length(m) do
a[length(m)-i+1]:=get(m[i]);
for i:=100 downto 1 do
if a[i]<>0 then
begin
gex:=i;
break;
end;
t:=0;
for i:=1 to 30 do
begin
if yes(a) then break;
add(a);
inc(t);
end;
if yes(a) then write(t)
else write('Impossible');
end.