using System;

namespace _06_NToPSystem
{
    public class Program
    {
        public static void Main()
        {
            int n = int.Parse(Console.ReadLine());
            int p = int.Parse(Console.ReadLine());

            string input;
            while ((input = Console.ReadLine()) != "END")
            {
                int decimalResult = 0;

                for (int i = 0; i < input.Length; i++)
                {
                    int currentNumber = (int)char.GetNumericValue(input[input.Length - i - 1]);

                    decimalResult += currentNumber * (int)Math.Pow(n, i);
                }

                string binary = string.Empty;

                while (decimalResult > 0)
                {
                    int currentNumber = decimalResult % p;

                    if (p > 10 && currentNumber > 9)
                    {
                        char symbol = (char)('A' + currentNumber - 10);
                        binary += symbol;
                    }
                    else
                    {
                        binary += currentNumber;
                    }

                    decimalResult = decimalResult / p;
                }

                for (int i = 0; i < binary.Length; i++)
                {
                    Console.Write(binary[binary.Length - i - 1]);
                }
                Console.WriteLine();
            }
        }
    }
}