/*
 Author: 曹北健(37509)
 Result: AC Submission_id: 5207186
 Created at: Tue Mar 14 2023 10:15:51 GMT+0800 (China Standard Time)
 Problem: 6695  Time: 5 Memory: 1508
*/

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include <math.h>
int main(){
#ifdef LINUX_DEBUG
    freopen("../input.txt", "r", stdin);
#endif
    int a[64] = { 0 }, T;

    char input[128] = { 0 };
    scanf("%d", &T);
    while(T--){
        long long base1, base2, s = 0, s2, tmp1;
        long long cur = 1;
        scanf("%lld%lld%s", &base1, &base2, input);
        //input no '-'
        int n = strlen(input), i;
        if(n == 1 && input[0] == '0'){
            puts("0");
            continue;
        }
        for(i = n - 1;i >= 0;i--){
            if(isupper(input[i])){
                s += (input[i] - 'A' + 10) * cur;
            }
            else{//digit
                s += (input[i] - '0') * cur;
            }
            cur *= base1;
        }
        n = 0;
        //printf("%lld\n", s);
        s2 = s;
        while(s2){
            tmp1 = s2 % base2;
            s2 /= base2;
            if(tmp1 < 0){//base2<0
                s2 += 1;tmp1 -= base2;
            }
            a[n] = tmp1;
            n++;
        }
        while(n--){
            if(a[n] >= 10){
                putchar(a[n] - 10 + 'A');
            }
            else{
                putchar('0' + a[n]);
            }
        }
        putchar('\n');
    }
    return 0;
}