#include <cstdlib>
#include <iostream>
#include <math.h>
using namespace std;
int dectox(int x,int dec,char ar[])
{
    int n,l;
    if(dec<x)
    {
             ar[0]=(dec < 10) ? dec + 48 : dec + 87;
             return ( 1 );
             }
     n=dec%x;
     l=dectox( x , dec / x , ar );
     ar[l]=(n < 10) ? n + 48 : n + 87;
     return(l + 1);
     
 }
 int xtodec(int x,char ar[],int len,int n)
 {
     if(n==len)
     {
               if(ar[0] < 97)
                        return (ar[len] - 48);
               else
                   return (ar[len] - 87);
               }
     long int dec,pow=1;
     for(int i=1;i<=len-n;i++)
     pow*=x;
     dec=xtodec(x,ar,len,n+1);
     if(ar[n] < 97)
               dec+=( ar[n] - 48 )* pow;
               else
               dec+=( ar[n] - 87 )* pow;
     return dec;
 
 }
int chartonum(char ar[])
 {
      int num=0;
      for(int i=0;ar[i]!=0;i++)
              num=(num*10)+(ar[i]-48);
      return num;
 }
 void reset(char ar[])
 {
      for(int i=0;i<40;i++)
      ar[i]=0;
 }
int main(int argc, char *argv[])
{
    int n,a,b,test,l;
    char ar[40]={};
    cin>>test;
    for(int i=0;i<test;i++)
    {
			n=a=b=l=0;
            cin>>ar>>b>>a;
            if(b==10)
            {
                     n=chartonum(ar);
            }
            else
            {
                for(int i=0;i<40;i++)
                        if(ar[i]==0)
                        {
                                       l=i-1;
                                       break;             
                        }
                n=xtodec(b,ar,l,0);
            }
            reset(ar);
            dectox(a,n,ar);
            cout<<ar<<endl;
            reset(ar);     
    }
    
}