#include
#include
#include
int IsPalindrome(const char* beg, const char* end)
{
while(beg < end)
if(*beg++ != *--end)
return 0;
return 1;
}
inline void Swap(char* lhs, char* rhs)
{
char tmp = *lhs;
*lhs = *rhs;
*rhs = tmp;
}
void Reverse(char* beg, char* end)
{
while(beg < end)
Swap(beg++, --end);
}
int ToDecimal(int n, const char* num)
{
const char* p = num + strlen(num) - 1;
int dec = 0;
int radix = 1;
while(p >= num)
{
dec += (*p-- - '0') * radix;
radix *= n;
}
return dec;
}
void Revert(int dec, int n, char* buf)
{
char* p = buf;
int tmp;
if(n == 16)
sprintf(buf, "%x", dec);
else
{
while(dec > 0)
{
tmp = dec % n;
dec /= n;
*p++ = tmp + '0';
}
Reverse(buf, buf + strlen(buf));
}
}
int IsInputOK(int n, char* num)
{
if(n <= 2 || n > 10 && n != 16)
return 0;
if(!strlen(num))
return 0;
if(n != 16)
while(*num)
if(*num++ - '0' > n)
return 0;
else
for(; *num; ++num)
if(*num - '0' > n || toupper(*num) < 'A' || toupper(*num) > 'F')
return 0;
return 1;
}
int SearchAndStepNext(int n, char* num)
{
int step = 0;
int dec;
if(!IsInputOK(n, num))
{
puts("Invalid input!");
return 999;
}
dec = ToDecimal(n, num);
while(!IsPalindrome(num, num + strlen(num)) && step <= 30)
{
Reverse(num, num + strlen(num));
dec += ToDecimal(n, num);
Revert(dec, n, num);
step++;
}
return step;
}
#define MAXLEN 32
int main()
{
char num[MAXLEN] = {0};
int result[100] = {-1};
int n, step, i = 0, j;
while(scanf("%d%s", &n, num) && i < 100)
{
if(!n)
break;
if((step = SearchAndStepNext(n, num)) <= 30)
result[i++] = step;
else
++i;
memset(num, 0, MAXLEN);
}
for(j = i, i = 0; i < j; ++i)
if(result[i] != -1)
printf("step = %d\n", result[i]);
else
puts("Impossible!");
return 0;
}