#include <stdio.h>
#include <string.h>
/*INVALID INPUTS:
(1) if input contains characters not within the set of characters of that particular base
(e.g., base 3 with 99291 is invalid because only 0-2 are valid characters for that base)
(e.g., base 16 with 2233AALDDEFF is invalid because only 0-9 and A-F are valid characters for that base)
(2) if input contains characters not within the set of characters valid, i.e., some characters are not from the set containing 0-9 and A-Z.
(e.g., for whatever base, input 11ADDD_LO is invalid since it contains '_')
(e.g., for whatever base, input 3998a is invalid since it contains a lowercase letter)
(e.g., for whatever base, input 889ADFO SLDO is invalid since it contains a space)

new limit ? 2^31 -1 = 2 147 483 647 */
int convertVal(char num[],long int i,long int len){

        if(i>=len) return 0;

        num[i]=(num[i]<65)?num[i]-48:num[i]-55;
        convertVal(num,i+1,len);

        return 0;
}

int checkIfValid(char num[], int n){
    int i;
    int len = strlen(num);
    for(i = 0; i < len; i++){
    if(num[i] < '0' || num[i] > '9' || num[i] < 'A' || num[i] > 'Z'){
        printf("invalid");
        return -1;}
    }
    return 0;
}
long int toDecimal(char num[],long int n,long int i,long int len){

        long int pow=1,j;

        if(i>=len) return 0;

        for(j=1;j<len-i;j++)
                pow=pow*n;

        return num[i]*pow+toDecimal(num,n,i+1,len);
}

long int newBase(long int dec,long int m,long int pow){

        long int j,power=1;

        if(pow<0) return 0;

        for(j=0;j<pow;j++)
                power=power*m;

        printf("%c",(dec/power<10)?dec/power+48:dec/power+55);
        newBase(dec-(dec/power)*power,m,pow-1);

        return 0;
}
int main(){

        char num[100];
        long int n,m,i=0,pow=1;//n is the base of the number ; m is the new base ; num is the number to be converted
        unsigned long long int temp,dec;
        int x=1,y;
        scanf("%d",&y);

        while (x<=y){
        scanf("%ld %ld %s",&n,&m,num);

        long int len = strlen(num);

        convertVal(num,0,len);
        checkIfValid(num,n);
        dec=toDecimal(num,n,0,len);

        while(dec>=pow*m){
                pow=pow*m;
                i++;
        }

        temp = newBase(dec,m,i);
        printf("\n");


        x++;
        }
     return 0;
}