#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<string>
char s[50];
int k,size;
using namespace std;
struct node
{
int a[50];
int size;
};
void readdata()
{
char c=0;
scanf("%d\n",&k);
while(c!=-1)
{
c=getchar();
if(c==-1) break;
if(isdigit(c)==0)
{
s[size]=c-'A'+10+'0';
size++;
continue;
}
s[size]=c;
size++;
}
}
node jia(node x,node y)
{
node t;
for(int i=1;i<=x.size;i++)
{
t.a[i]=x.a[i]+y.a[i];
}
for(int i=1;i<x.size;i++)
{
t.a[i+1]+=t.a[i]/k;
t.a[i]%=k;
}
t.size=x.size;
while(t.a[t.size]>=k)
{
t.size++;
t.a[t.size]=t.a[t.size-1]/k;
t.a[t.size-1]%=k;
}
return t;
}
bool check(node t)
{
for(int i=1;i<t.size/2+1;i++)
{
if(t.a[i]!=t.a[t.size-i+1]) return false;
}
return true;
}
void print(node t)
{
for(int i=1;i<=t.size;i++)
printf("%d",t.a[i]);
printf("\n");
}
void work()
{
node x,y,sum;sum.size=size;
for(int i=1;i<=size;i++) sum.a[i]=s[i-1]-'0';
if(check(sum)==true){printf("0");exit(0);}
for(int i=1;i<=30;i++)
{
for(int j=1;j<=sum.size;j++)
{
x.a[j]=sum.a[j];
}
x.size=sum.size;
for(int j=sum.size;j>0;j--)
{
y.a[sum.size+1-j]=sum.a[j];
}
y.size=sum.size;
sum=jia(x,y);
// print(sum);
if(check(sum)==true){printf("%d",i);exit(0);}
}
printf("Impossible");
}
int main()
{
readdata();
work();
return 0;
}