[NOIP1999]回文数

#include<stdio.h>
#include<stdbool.h>
#include<string.h>
bool judge(char*p,int n)//判断回文数
{
    for(int i=0;i<n/2;i++)
    {
        if(p[i]!=p[n-1-i])
            return false;
    }
    return true;
}
void STEP(char*M1,int len,int N)
{
    int m=0,n=0;
    char M2[100];
    char* p=M2;
   for(int i=0;i<len;i++)
    {
       int n1,n2;
       if(M1[i]>='0'&&M1[i]<='9')
           n1=M1[i]-48;
       else
           n1=M1[i]-'A'+10;
       if(M1[len-i-1]>='0'&&M1[len-i-1]<='9')
           n2=M1[len-i-1]-48;
       else
           n2=M1[len-i-1]-'A'+10;
       n=n1+n2;
       if(m!=0)
           n++;
       m=n/N;
       n=n%N;
       if(n<10)
           *p=(char)(n+48);
       else
            *p='A'+n-10;
        p++;
    }
    if(m==1)
        *p=(char)(m+48),p++;
    *p='\0';
    int len2=strlen(M2);
    for(int i=0;i<len2;i++)
    {
        M1[i]=M2[len2-1-i];
    }
     M1[len2]='\0';
}

int main()
{
    int N,i;
    char M1[100]; 
    scanf("%d%s",&N,M1);
    int len=strlen(M1);
    for( i=0;i<31;i++)
    {
        STEP(M1,strlen(M1),N);
        if(judge(M1,strlen(M1)))
            break;
    }
    if(i<31)
        printf("STEP=%d",i+1);
    else
         printf("Impossible!");
    return 0;
}

#include <stdio.h>
int pld(char M[], int* l) {//判断回文数
    int left = 0;
    int right = *l;
    for (; left < right; left++, right--) {
        if (M[left] != M[right])
            return 1;
    }
    return 0;
}
void add(char M[], int* l, int n) {//对数字进行处理（反序相加，1-16进制皆可）
    int i = 0;
    int j = *l;
    int sum = 0;
    char M1[100];
    for (i = 0; i <= *l; i++, j--)//创建新数组保存反序后的数
        M1[i] = M[j];
    for (i = 0; i <= *l; i++) {//处理十进制以上的数
        if (M[i] > 57)
            M[i] -= 7;
        if (M1[i] > 57)
            M1[i] -= 7;
    }
    for (i = 0; i <= *l; i++) {
        sum = M[i] + M1[i] - 96;
        M[i] = (sum % n + 48);//两个数相加取模n进制
        if (i == *l) {//判断如果两个数的首尾相加有进位，l就加一（l记录这个数有几位数）
            if ((sum / n) != 0) {
                M[i + 1] = (sum / n + 48);
                (*l)++;
            }
            break;
        }
        M[i + 1] = (sum / n + 48) + M[i + 1] - 48;//两个数相加的进位加到前一位去（没有进位就是加0）
    }
    for (i = 0; i <= *l; i++) {//处理十进制以上的数
        if (M[i] > 57)
            M[i] += 7;
    }
}
int main() {
    int n = 0;
    int l = 0;
    int step = 0;
    char M[100];
    scanf("%d", &n);
    getchar();
    int i = 0;
    do {
        M[i] = getchar();//将数字读入数组里
        i++;
    } while (M[i - 1] != '\n');
    i -= 2;
    l = i;//l是记录这个数有几位数
    int left = 0;
    int right = l;
    do {//将数组里数字反序（这里是方便后面进位才反序的，实际的反序相加处理在后面的函数里）
        int tmp = 0;
        tmp = M[left];
        M[left] = M[right];
        M[right] = tmp;
    } while (left++ < right--);
    while (pld(M, &l)) {//如果不是回文数就继续反序相加处理
        add(M, &l, n);
        step++;
        if (step > 30)//处理步数大于30就跳出循环
            break;
    }
    if (step <= 30)
        printf("STEP=%d", step);
    else
        printf("Impossible!");
    return 0;
}

#include <iostream>
#include <math.h>
#include <string>
using namespace std;
//different base number add fuction
long long ReturnAdd(long long number) {
    long long returnNumber = 0;
    while (number) {
        returnNumber *= 10;
        returnNumber += number % 10;
        
        number /= 10;
    }
    return returnNumber;
}

long long ReturnNumberAdd(int base, long long number) {
    // return
    long long returnNumber = ReturnAdd(number);
    long long baseNumber = 0, baseReturnNumber = 0;
    long long i = 0;
    while (number) {
        baseNumber += (number % 10) * pow(base, i);
        baseReturnNumber += (returnNumber % 10) * pow(base, i);
        i += 1;
        number /= 10;
        returnNumber /= 10;
    }
    long long sumNumber = baseNumber + baseReturnNumber; long long aaa = sumNumber;
    long long sumBaseNumber = 0;long long count = 0;
    while (sumNumber) {
        sumBaseNumber += (sumNumber % base) * pow(10, count);
        sumNumber /= base;
        count += 1;
    }
    return sumBaseNumber;
}
//
long long ReturnSixteenNumber(long long number) {
    long long returnNumber=0;
    while (number) {
        returnNumber *= 16;
        returnNumber += (number % 16);
        number /= 16;
    }
    return returnNumber;
}

long long ReturnSixteenAdd(long long number) {
    long long returnNumber = 0;
    long long temp = number;
    // return number
    while (number) {
        returnNumber *= 16;
        returnNumber += (number % 16);
        number /= 16;
    }
    long long sumNumber = returnNumber + temp;
    return sumNumber;
}
//
int main() {
    long long a, b, step=0;
    cin >> a;
    if (a == 16) {
        cin >> hex >> b;
        while (step >= 0) {
            step += 1;
            if (ReturnSixteenNumber(ReturnSixteenAdd(b)) == ReturnSixteenAdd(b))
            {
                cout << "STEP=" << step;
                break;
            }
            if (step >= 30) {
                cout << "impossible!";
                break;
            }
            b = ReturnSixteenAdd(b);
        }
    }
    else {
        cin >> b;
        while (step >= 0) {
            step += 1;
            if (ReturnAdd(ReturnNumberAdd(a, b)) == ReturnNumberAdd(a, b))
            {

                cout << "STEP=" << step;
                break;
            }
            if (step >= 30) {
                cout << "Impossible!";
                break;
            }
            b = ReturnNumberAdd(a, b);
        }
    }
    return 0;
}
// 64 位输出请用 printf("%lld")

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef unsigned long long ull;

// 逆序，只能10进制数
ull reverse(ull n) {
    ull sum = 0;
    while (n != 0) {
        sum = sum * 10 + n % 10;
        n /= 10;
    }
    return sum;
}

// 逆序，只能16进制数
ull reverse_16(ull n) {
    int i, len = 0;
    ull m = n;
    char tmp;
    while (m != 0) {
        len++;
        m = m / 10;
    }
    char* str = (char*)calloc(len + 1, sizeof(char));
    sprintf(str, "%llX", n);
    len = 0;
    while (str[len] != '\0')
        len++;
    // printf("逆序前：%s\n",str);
    for (i = 0; i < len / 2; i++) {
        // printf("*(str+i)=%c *(str+(len-i))=%c\n",*(str+i),*(str+(len-1-i)));
        tmp = *(str + i);
        *(str + i) = *(str + (len - 1 - i));
        *(str + (len - 1 - i)) = tmp;
    }
    // printf("逆序后：%s\n",str);
    sscanf(str, "%llX", &m);
    // printf("m=%llu\n", m);
    free(str);
    return m;
}

// 2<=n<=10 进制转10进制,
ull n2ten(ull a, int n) {
    ull y = 0, i = 1;
    while (a != 0) {
        y = y + (a % 10) * i;
        a /= 10;
        i = i * n;
    }
    return y;
}

// 10进制数转为n进制 2<=n<=10
ull ten2n(ull a, int n) {
    ull sum = 0;
    int str[100] = {0};
    int count = 0, i = 0;
    do {
        str[count] = a % n;
        a /= n;
        count++;
    } while (a != 0);
    for (i = count - 1; i >= 0; i--)
        sum = sum * 10 + str[i];
    return sum;
}

// 判断是否是回文数，只能是10进制数，1，是；0，不是
int isPalindrome(ull n) {
    int i, len = 0;
    ull m = n;
    while (m != 0) {
        len++;
        m = m / 10;
    }
    char* str = (char*)calloc(len + 1, sizeof(char));
    sprintf(str, "%llu", n);
    for (i = 0; i < len / 2; i++) {
        // printf("*(str+i)=%c *(str+(len-i))=%c\n",*(str+i),*(str+(len-1-i)));
        if (*(str + i) != *(str + (len - 1 - i))) {
            free(str);
            return 0;
        }
    }
    free(str);
    return 1;
}

// 判断是否是回文数，只能是16进制数，1，是；0，不是
int isPalindrome_16(ull n) {
    int i, len = 0;
    ull m = n;
    while (m != 0) {
        len++;
        m = m / 10;
    }
    char* str = (char*)calloc(len + 1, sizeof(char));
    sprintf(str, "%llX", n);
    //printf("len=%d %s\n", len,str);
    len = 0;
    while (str[len] != '\0')
        len++;
    //printf("len=%d %s\n", len,str);
    for (i = 0; i < len / 2; i++) {
        //printf("*(str+i)=%c *(str+(len-i))=%c\n", *(str + i), *(str + (len - 1 - i)));
        if (*(str + i) != *(str + (len - 1 - i))) {
            free(str);
            return 0;
        }
    }
    free(str);
    return 1;
}

int main() {
    ull a, ac;
    int b;
    ull tmp;
    int i = 0;
    scanf("%d", &b);
    if (b == 16) {
        scanf("%llX", &a);
    } else if (b >= 2 && b <= 10) {
        scanf("%llu", &a);
    }
    ac = a;
    if (b == 16) {
        while (1) {
            i++;
            tmp = ac + reverse_16(ac);
            //printf("10:%lld %d:%llX\n", tmp, b, tmp);

            if (isPalindrome_16(tmp)) {
                printf("STEP=%d\n", i);
                return 0;
            }
            if (i > 30) {
                printf("Impossible!");
                return 0;
            }
            ac = tmp;
        }
    } else {
        while (1) {
            i++;
            tmp = n2ten(ac, b) + n2ten(reverse(ac), b);
            //printf("10:%lld %d:%lld\n", tmp, b, ten2n(tmp, b));

            if (isPalindrome(ten2n(tmp, b))) {
                printf("STEP=%d\n", i);
                return 0;
            }
            if (i > 30) {
                printf("Impossible!");
                return 0;
            }
            ac = ten2n(tmp, b);
        }
    }

    return 0;
}

#include <iostream>
using namespace std;

string toNString(long long number, int base);
long long toDecimal(string number, int base);
string add(string number, int base);
bool huiWenShu(string number);

int main() {
    int n;
    string m;
    cin >> n >> m;
    for (int i = 0; i < 30; i++) {
        if (huiWenShu(m)) {
            cout << "STEP=" << i << endl;
            // cout << m << endl;
            return 0;
        }
        // cout << "step" << i << "\t" << m << endl;
        m = add(m, n);
    }
    cout << "Impossible!" << endl;
    return 0;
}

string toNString(long long number, int base) {
    string ret = "";
    while (number) {
        int remainder = number % base;
        if (remainder < 10) {
            ret = (char)(remainder + '0') + ret;
        } else {
            ret = (char)(remainder - 10 + 'A') + ret;
        }
        number /= base;
    }
    return ret;
}

long long toDecimal(string number, int base) {
    long long ret = 0;
    int len = number.length();
    for (int i = 0; i < len; i++) {
        if (number[i] >= '0' && number[i] <= '9') {
            ret = ret * base + number[i] - '0';
        } else {
            ret = ret * base + number[i] - 'A' + 10;
        }
    }
    return ret;
}

string add(string number, int base) {
    long long n1 = toDecimal(number, base);
    long long n2 = toDecimal(string(number.rbegin(), number.rend()), base);
    return toNString(n1 + n2, base);
}

bool huiWenShu(string number) {
    bool ret = true;
    int len = number.length();
    for (int i = 0; i < len / 2; i++) {
        if (number[i] != number[len - i - 1]) {
            ret = false;
        }
    }
    return ret;
}

#include <cmath>
#include <iostream>
using namespace std;
#define A 11;
#define B 12;
#define C 13;
#define D 14;
#define E 15;
long long reversl(long long a)
{
    long sum = 0;
    while (a) 
    {
        sum = sum * 10 + a % 10;
        a /= 10;
    }
    return sum;
}
long long digit(long a)
{
    long count = 0;
    while (a) 
    {
        a /= 10;
        count++;
    }
    return count;
}
long long palindrome(long long a, long long b)
{
    long long  ret = reversl(b);
    long sum = 0;
    int tmp = 0;
    int count = 0;
    int scr = digit(b);
    for (int i = 0; i <= scr; i++) 
    {
        sum += ((ret % 10 + b % 10 + tmp)) % a * pow(10, i);
        tmp = (ret % a + b % a +tmp) / a;
        ret /= 10;
        b /= 10;
    }
    return sum;
}
int main()
{
    int n, m; 
    cin >> n >> m;
    int count = 0;
    if (n != 16) 
    {
        long long ret = palindrome(n, m);
        long long tmp = reversl(palindrome(n, m));
        while (ret != tmp) 
        {
            count++;
            ret = palindrome(n, ret);
            tmp = reversl(ret);
            if (count >= 30) 
            {
                cout << "Impossible!" << endl;
                return 0;
            }
        } 
    }
    else 
    {
        count = 5;
    }
    cout << "STEP=" << count+1 << endl;
}

package main

import (
    "fmt"
    "strconv"
)

func reverse(s string) string {
    str := ""
    for _, k := range s {
        str = string(k) + str
    }
    return str
}
func toDecimal(s string, n int) int {
    res, length, cur := 0, len(s), 1
    for i := length - 1; i >= 0; i-- {
        if s[i] <= '9' {
            res += int(s[i]-'0') * cur
        } else if s[i] <= 'Z' {
            res += (int(s[i]-'A') + 10) * cur
        } else {
            res += (int(s[i]-'a') + 10) * cur
        }
        cur *= n
    }
    return res
}
func main() {
    var (
        n int    // 进制数
        m string // 数
    )
    fmt.Scan(&n, &m)
    for i := 1; i <= 30; i++ {
        rm := reverse(m)
        m10, rm10 := toDecimal(m, n), toDecimal(rm, n)
        m = strconv.FormatInt(int64(m10+rm10), n)
        if reverse(m) == m {
            fmt.Printf("STEP=%d", i)
            return
        }
    }
    fmt.Println("Impossible!")
}

def dec_to_m(num, m):
    # 十进制转任意进制
    a = []
    while num != 0:
        temp = num % m
        if temp > 9:
            temp = chr(temp-10 + ord("A"))
        a.append(str(temp))
        num //= m
    return "".join(a)
if __name__ == "__main__":
    m = int(input())
    n = input()
    count = 0
    while True:
        temp = int(n, m) + int(n[::-1], m)
        n = dec_to_m(temp, m)
        count = count + 1
        if count>30:
            print("Impossible!")
            break
        if n == n[::-1]:
            break
    if count <= 30:
        print("STEP=%d" % count)

#include <stdbool.h>
#include <stdio.h>
long sum_decimal(char *p, long length, long radix);
long to_radixOfN(char *p, long sum, long radix);
_Bool isPalindrome(char *p, long length);
//有一个用例是10进制89，需要24步，如果用int很快就不够，会高位截断，结果不对，所以用long;
int main() {
    char arr[101] = {0}, temp;
    long radix, steps = 0, index = 0, sum = 0, new_index = 0;
    scanf("%ld", &radix);
    getchar();
    while((temp = getchar()) != '\n'){
        arr[index++] = temp;
    }
    while(steps <= 30){
        sum = sum_decimal(arr, index, radix);
        steps++;
        new_index = to_radixOfN(arr, sum, radix);
        if(isPalindrome(arr, new_index)){
            printf("STEP=%ld\n", steps);
            break;
        }
        index = new_index;
    }
    if(steps > 30){
        printf("Impossible!");
    }
    return 0;
}

long sum_decimal(char *p, long length, long radix){
    long result = 0, multi = 1;
    for(long i = 0; i < length; i++){
        if(p[i] >= '0' && p[i] <= '9'){
            result += multi * (p[i] - '0');
        } else {
            result += multi * (p[i] - 55);
        }
        multi *= radix;
    }
    multi = 1;
    for(long i = length - 1; i >= 0; i--){
        if(p[i] >= '0' && p[i] <= '9'){
            result += multi * (p[i] - '0');
        } else {
            result += multi * (p[i] - 55);
        }
        multi *= radix;
    }
    return result;
}
long to_radixOfN(char *p, long sum, long radix){
    long length = 0;
    while(sum){
        if(sum % radix >= 10){
            p[length++] = sum % radix + 55;
        } else {
            p[length++] = sum % radix + '0';
        }       
        sum /= radix;
    }
    return length;
}
_Bool isPalindrome(char *p, long length){
    long left = 0, right = length - 1;
    while(left < right){
        if(p[left] == p[right]){
            left++, right--;
        } else {
            return false;
        }
    }
    return true;
}

#include<stdio.h>
#include<stdbool.h>
#include<math.h>
#include<string.h>
char c[100] = {0};
bool IsPalindrome(char* p, int len)
{
	
	int left = 0;
	int right = len - 1;
	while ((left) < (right))
	{
		if (p[left++] != p[right--])
			return false;
	}
	return true;
}
int getInt(char n)//将'0'-'9'转换为0-9；'a'-'z'转换成10-35
{
	if (n >= '0' && n <= '9')
		return n - '0';
	else
	{
		return n - 'A' + 10;
	}
}
char getChar(int n)//将0-9转换为'0'-'9';a-z转换成’a'-‘z'
{
	if (n >= 0 && n <= 9)
		return n + '0';
	else
		return n - 10 + 'A';
}
void Add(char* a,int N,int len)
{
	int sum1 = 0;
	int sum2 = 0;
	int tail = 0;
	int begin = 0;
	int end = len - 1;
	int i = 0;
	while (end >= 0)
	{
		sum1 = getInt(a[begin]);
		sum2 = getInt(a[end]);
		c[i] = getChar((sum1+sum2+tail)%N);
		tail = (sum1 + sum2 + tail) / N;
		end--;
		begin++;
		i++;

	}
	while (tail > 0)
	{
		c[i] = getChar(tail % N);
		tail /= N;
		i++;
	}

}
int main()
{
	char a[100] = {0};
	int N = 0;
	scanf("%d", &N);
	getchar();
	scanf("%s", a);
	int len = strlen(a);
	if (IsPalindrome(a, len))
	{		printf("STEP=%d\n",1);
	return 1;
}
	int count = 0;
	while (!IsPalindrome(a,len))
	{
		Add(a,N,len);
		strcpy(a,c);
		len = strlen(c);
		count++;
		if (count >= 31)
		{
			printf("Impossible!\n");
			return 0;
		}

	}

	printf("STEP=%d\n",count);
	return 0;
}

#include<stdio.h>
void transform(char ch1[100],int ch_1[100],int i)
{
    for (int j = 0; j <= i; j++)
    {
        switch (ch1[j])
        {
        case 'A':
            ch_1[j] = 10;
            break;
        case 'B':
            ch_1[j] = 11;
            break;
        case 'C':
            ch_1[j] = 12;
            break;
        case 'D':
            ch_1[j] = 13;
            break;
        case 'E':
            ch_1[j] = 14;
            break;
        case 'F':
            ch_1[j] = 15;
            break;
        default:
            ch_1[j] = ch1[j] - '0';
            break;
        }
    }
}
int Add(char ch1[100], char ch2[100],char sum[100],int i,int n)
{
    //对数组进行变换，由char型变为int型
    int ch_1[100] = { 0 };
    int ch_2[100] = { 0 };
    transform(ch1, ch_1, i);
    transform(ch2, ch_2, i);
    int j = 0;
    while (i>=0)
    {
        int tmp = ch_1[j] + ch_2[j];
        if (tmp < n&&n>10)
        {
            switch (tmp)
            {
            case 10:
                sum[j] = 'A';
                break;
            case 11:
                sum[j] = 'B';
                break;
            case 12:
                sum[j] = 'C';
                break;
            case 13:
                sum[j] = 'D';
                break;
            case 14:
                sum[j] = 'E';
                break;
            case 15:
                sum[j] = 'F';
                break;
            default:
                sum[j] = tmp + '0';
                break;
            }
        }
        else if (tmp<n&&n<=10)
        {
            sum[j] = tmp + '0';
        }
        else if (tmp >= n && n > 10)
        {
            ch_1[j + 1] += 1;
            switch (tmp%n)
            {
            case 10:
                sum[j] = 'A';
                break;
            case 11:
                sum[j] = 'B';
                break;
            case 12:
                sum[j] = 'C';
                break;
            case 13:
                sum[j] = 'D';
                break;
            case 14:
                sum[j] = 'E';
                break;
            case 15:
                sum[j] = 'F';
                break;
            default:
                sum[j] = tmp%n + '0';
                break;
            }
        }
        else if (tmp >= n && n <= 10)
        {
            ch_1[j + 1] += 1;
            sum[j] = tmp % n+'0';
        }
        i--;
        j++;
    }
    if (ch_1[j] > 0)
        sum[j] = ch_1[j] + '0';
    else
        j = j - 1;
    //再颠倒
    int left = 0;
    int right = j;
    while (left <= right)
    {
        char ret = sum[left];
        sum[left] = sum[right];
        sum[right] = ret;
        left++;
        right--;
    }
    return j;
}
int is_pan(char sum[100],int j)
{
    int left = 0;
    int right = j;
    while (left <= right)
    {
        if (sum[left] != sum[right])
            return 0;
        left++;
        right--;
    }
    return 1;
}
int main()
{
    //搞明白自己的错误点，逆序和进制没有关系，不能把所有的数转化为10进制再运算。
    //由于有16等进制的存在，所以要获取字符，而不是数字
    int n;
    char ch1[100] = { 0 };
    char ch2[100] = { 0 };
    int i = 0;
    int count = 1;
    scanf("%d", &n);
    getchar();
    while (scanf("%c", &ch1[i])!=EOF)
    {
        if (ch1[i] == '\n')
            break;
        i++;
    }
    i = i - 1;
    //逆序，逆序之后再做进制运算
    //用一个新数组存
    while (1)
    {
        char sum[100] = { 0 };
        int j = 0;
        int tmp = i;
        for (j = 0; j <= i; j++)
        {
            ch2[j] = ch1[tmp];
            tmp--;
        }
        int ret = Add(ch1, ch2, sum, i, n);
        //已经得到sum[];
        int out = is_pan(sum, ret);
        if (out == 1)
        {
            printf("STEP=%d\n", count);
            break;
        }
        else
        {
            i = ret;
            for (j = 0; j <= ret; j++)
            {
                ch1[j] = sum[j];
            }
            count++;
            if (count > 30)
            {
                printf("Impossible!\n");
                break;
            }
            continue;
        }

    }
    return 0;
}

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String a = sc.nextLine();
        String b = sc.nextLine();
        int count = 0;
        while (!isHw(b)){
            count++;
            if (count > 30){
                break;
            }
            b = toString(Integer.valueOf(a),String.valueOf(toInt(Integer.valueOf(a), b) + toInt(Integer.valueOf(a), reverse(b))));
        }
        if (count > 30){
            System.out.println("Impossible!");
        } else {
            System.out.println("STEP=" + count);
        }
    }

    private static String reverse(String b){
        return new StringBuilder(b).reverse().toString();
    }

    private static long toInt(int a, String b){
        return Long.valueOf(b, a);
    }

    private static String toString(int a, String b){
        return Long.toString(Long.valueOf(b), a);
    }

    private static boolean isHw(String str){
        return str.equals(new StringBuilder(str).reverse().toString());
    }
}

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
long long ten(char m[], int n, int len)
{
    long long sum = 0;
    int i = 0, j = 0;
    int arr[100];
    for (i = len - 1; i >= 0; i--)//把0~10进制之间的数转化成10进制
    {
        if (m[i] == 'A'|| m[i] == 'a')
        {
            arr[i] = 10;
        }
        else if (m[i] == 'B' || m[i] == 'b')
        {
            arr[i] = 11;
        }
        else if (m[i] == 'C' || m[i] == 'c')
        {
            arr[i] = 12;
        }
        else if (m[i] == 'D' || m[i] == 'd')
        {
            arr[i] = 13;
        }
        else if (m[i] == 'E' || m[i] == 'e')
        {
            arr[i] = 14;
        }
        else if (m[i] == 'F' || m[i] == 'f')
        {
            arr[i] = 15;
        }
        else
        {
            arr[i] = m[i] - '0';
        }
        sum += arr[i] * pow(n, j);
        j++;
    }
    return sum;
}
void Back(char arr[], int n, long long x)//把10进制数转化为n进制数
{
    int i = 0, j = 0;
    long long ret = x;
        while (ret)
        {
            ret /= n;
            i++;
        }//求出x是i位数
        ret = x;
        for (j = i - 1; j >= 0; j--)
        {
            arr[j] = (ret % n) + '0';
            ret /= n;
        }
    arr[i] = '\0';
}

void swap(char m[], char arr[], int len)
{
    int i = 0, j = 0;
    for (i = len - 1; i >= 0; i--)
    {
        arr[j] = m[i];
        j++;
    }
    arr[len] = '\0';
}
int Palindrome(char arr[])
{
    int len = strlen(arr);
    int left = 0, right = len - 1;
    //78287
    while (left <= right)
    {
        if (arr[left] == arr[right])
        {
            left++;
            right--;
        }
        else
        {
            return 0;
        }
    }
    return 1;
}
int main()
{
    int n = 0;
    char m[100];
    char arr1[100];
    scanf("%d", &n);
    scanf("%s", &m);
    char arr2[100];
    int i = 0;
    long long sum = 0;
    int step = 0;
    while (1)
    {
        int len = strlen(m);
        step++;
        swap(m, arr2, len);//把倒过来的m放在arr2中
        //printf("%s ", m);
        //printf("%s \n", arr2);
        if (n!=16&&n!=10)
        {
            sum = ten(m, n, len) + ten(arr2, n, len);
            Back(arr1, n, sum);//把加一起的结果放在arr1中
        }
        else if (n==10)
        {
            sum = ten(m, 10, len) + ten(arr2, 10, len);
            Back(arr1, 10, sum);
        }
        else if(n==16)
        {
            sum = ten(m, 16, len) + ten(arr2, 16, len);
            sprintf(arr1, "%x", sum);//库函数：把十进制数转化为16进制
        }
        //printf("%s\n", arr1);
        //把m重新赋值为arr1
        len = strlen(arr1);
        //printf("%d\n", len);
        for (i = 0; i < len; i++)
        {
            m[i] = arr1[i];
        }
        m[len] = '\0';
        //printf("%s\n", m);
        //判断是否回文
        if (Palindrome(m) == 1 && step <= 30)
        {
            printf("STEP=%d", step);
            return 0;
        }
        else if (step > 30)
        {
            printf("Impossible!");
            return 0;
        }
    }
    return 0;
}