#include<cstdio>

 #include<cstring>

 #include<stack>

 #define MAXN 20

 using namespace std;

 stack<int> ans;

 int t[MAXN];

 char OldData[MAXN];

 int m;

 void trans()

 {

     int i,len,k=;

     len=strlen(OldData);

     for(i=len-;i>=;i--) t[len--i] = OldData[i] - (OldData[i]<='' ?  : (OldData[i]<'a' ?  : ));

     while(len)

     {

         for(i=len-;i>=;i--)

         {

             t[i-]+=t[i]%m*;

             t[i]/=m;

         }

         ans.push(t[]%m);

         t[]/=m;

         while(len> && !t[len-]) len--;

     }

     while(!ans.empty())

     {

         printf("%c",ans.top() + (ans.top()< ? '' : (ans.top()< ?  : )));

         ans.pop();

     }

     printf("\n");

 }

 int main()

 {

     while(scanf("%s",OldData)!=EOF)

     {

         scanf("%d",&m);

         int len=strlen(OldData);

         for(int i=;i<len;i++)

         {

             if(OldData[i]>='a' && OldData[i]<='j') OldData[i]=OldData[i]-'a'+'';

             else OldData[i]=OldData[i]-'k'+'A';

         }

         trans();

     }

 }