//Start: 2024-11-11 19:15:48
#include<bits/stdc++.h>
#define For(i,j,k) for(int i=(j);i<=(k);++i)
#define ForDown(i,j,k) for(int i=(j);i>=(k);--i)
#define Debug(fmt, args...) fprintf(stderr,"(func %s, line #%d): " fmt, __func__, __LINE__, ##args),fflush(stderr)
#define debug(fmt, args...) fprintf(stderr,fmt,##args),fflush(stderr)
#define within :
#define LJY main
using namespace std;
typedef long long ll;
const int N=1505;
mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
inline int read(){
  char ch=getchar();int x=0,f=1;
  while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
  while(ch>='0'&&ch<='9')
    x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
  return x*f;
}
int a[N],b[N],tot,c[N],x,y;
char s[N];
char itoc(int x){
  if(x<10) return x+'0';
  else if(x<36) return x-10+'A';
  else return x-36+'a';
}
int ctoi(char x){
  if(x>='0'&&x<='9') return x-48;
  else if(x>='A'&&x<='Z') return x-'A'+10;
  else return x-'a'+36;
}
signed LJY(){
  x=read();y=read();scanf("%s",s+1);
  int len=strlen(s+1);
  For(i,1,len) a[i]=ctoi(s[i]);
  reverse(a+1,a+1+len);
  while(len){
    For(i,1,len) c[i]=0;
    int now=0;
    ForDown(i,len,1){
      now=now*x+a[i];
      c[i]=now/y;now%=y;
    }b[++tot]=now;
    while(len&&!c[len]) len--;
    For(i,1,len) a[i]=c[i];
  }ForDown(i,tot,1) putchar(itoc(b[i]));
  return 0;
}