#include<stdio.h>
#include<string.h>

void liczymy(int cyfra, int system2)
{
    int wyniczek;
    char litera;
    if(cyfra==0)
        return;

    wyniczek=cyfra%system2;
    cyfra/=system2;
    liczymy(cyfra,system2);

    if(wyniczek<10)
        printf("%d",wyniczek);
    else
    {
        litera=wyniczek+55;
        printf("%c",litera);
    }
}
int main()
{

    char slowo[20];
    char klucz[]="CONVERT";
    char liczba[100];

    int wynik=0,system1,p=1,system2,cyfra,x,i,k,z,j;
    scanf("%d",&z);
    for(j=0;j<z;j++)
    {
        wynik=0;
        p=1;
        scanf("%s",&slowo);
        // if(strcmp(slowo, klucz) ==0)

        //    printf("podaj system1");
        scanf("%d",&system1);
        //    printf("podaj system2");
        scanf("%d",&system2);
        //    printf("podaj liczbe");
        scanf("%s",&liczba);

        for(i=strlen(liczba)-1;i>=0;i--)
        {
            if (liczba[i]>='0' && liczba[i]<='9')
                x=liczba[i]-'0';
            else
                x=liczba[i]-55;
            wynik+=x*p;
            p*=system1;
        }
        //    printf("%d",wynik);

        cyfra=wynik;
        //    printf ("liczba %d po zamianie na system %d wynosi:",cyfra,system2);

        if(cyfra)
        {
                    liczymy(cyfra,system2);
        } else printf("0");

        printf("\n");
    }


    return 0;


}