C++ :

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
using namespace std;
int n,sum;string s;
int a[1000]={0},b[1000]={0},c[1000]={0};//高精计算
void init(int a[])
{
	cin>>n>>s;
	a[0]=s.size();
	for(int i=1;i<=a[0];++i)
	{
		if(s[a[0]-i]>='0'&&s[a[0]-i]<='9')
		  a[i]=s[a[0]-i]-'0';
		else
		  a[i]=s[a[0]-i]-'A'+10;
	}
}
bool pd(int a[])
{
	for(int i=1;i<=a[0];++i)
	  if(a[i]!=a[a[0]-i+1])
		return false;
	return true;
}
void add(int a[])
{
	for(int i=1;i<=a[0];++i)
	  b[i]=a[a[0]-i+1];//顺序颠倒的数；
	for(int i=1;i<=a[0];++i)
	  a[i]+=b[i];
	for(int i=1;i<=a[0];++i)
	{
		a[i+1]+=a[i]/n;
		a[i]%=n;
	}
	if(a[a[0]+1]>0)
	  a[0]++;//防止进位过多及数组越界
}
int main()
{
	/*freopen("huiwen.in","r",stdin);
	freopen("huiwen.ans","w",stdout);*/
	init(a);
	pd(a);//如果输入的数就是回文数直接cout0
	if(pd(a)==true)
	  {
		cout<<0;
		//system("pause");
		return 0;
	  }
	while(sum<=30)
	{
		sum++;
		add(a);
		if(pd(a)==true)
		{
			cout<<sum;
			//system("pause");
			return 0;
		}
	}
	cout<<"Impossible";
	//system("pause");
	return 0;
}