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

long long int NtoTen (char value[], int n, int z, long long int sum, int ctr);
void TentoM (long long int sum, int m);
int toNum (char a);


int main ()
{
        int c;
        char value[100], ans[100];
        int n;
        int m;
        int i;
        int z;
        int ctr=0;
        long long int sum=0;

        do {
        printf ("Number of cases: ");
        scanf ("%d", &c);
        }
        while (c<1);

        for (i=0; i<c; i++)
        {
                printf ("Original base: ");
                scanf ("%d", &n);
                printf ("New base: ");
                scanf ("%d", &m);
                printf ("Input value: ");
                scanf ("%s", value);

                z=strlen(value);
                //printf ("Base10 equivalent is %d.\n", NtoTen (value, n, z, sum, ctr));
                sum= NtoTen (value, n, z, sum, ctr);
                printf("sum:%lld\n", sum);
                printf("\nNew: ");
                TentoM (sum, m);
                printf("\n");
        }
}

int toNum (char a)
{
        switch (a)
        {
                case '0': return 0;
                case '1': return 1;
                case '2': return 2;
                case '3': return 3;
                case '4': return 4;
                case '5': return 5;
                case '6': return 6;
                case '7': return 7;
                case '8': return 8;
                case '9': return 9;
                case 'A': return 10;
                case 'B': return 11;
                case 'C': return 12;
                case 'D': return 13;
                case 'E': return 14;
                case 'F': return 15;
                case 'G': return 16;
                case 'H': return 17;
                case 'I': return 18;
                case 'J': return 19;
                case 'K': return 20;
                case 'L': return 21;
                case 'M': return 22;
                case 'N': return 23;
                case 'O': return 24;
                case 'P': return 25;
                case 'Q': return 26;
                case 'R': return 27;
                case 'S': return 28;
                case 'T': return 29;
                case 'U': return 30;
                case 'V': return 31;
                case 'W': return 32;
                case 'X': return 33;
                case 'Y': return 34;
                case 'Z': return 35;
        }
}


long long NtoTen (char value[], int n, int z, long long int sum, int ctr)
{
        long long int dval;
        int g;
        long long int h=1;

        if (value[ctr]!='\0')
        {
                for (g=1; g<z; g++)
                {
                        h=h*n;
                }
                dval=toNum(value[ctr]);
                sum+=h*dval;
                //printf("%lld*%lld", dval, h);
                //printf("sum:%lld\n", sum);
                sum=NtoTen(value, n, z-1, sum, ctr+1);
                return sum;
        }
        else {return sum;}
}

void TentoM (long long int sum, int m)
{
        char str[36]={'0','1','2','3','4','5','6','7','8','9',
                  'A','B','C','D','E','F','G','H','I','J',
                  'K','L','M','N','O','P','Q','R','S','T',
                  'U','V','W','X','Y','Z'};

        if (sum/m<=0)
        {
            printf ("%c", str[sum%m] );
        }
        else
        {
                TentoM (sum/m, m);
                printf ("%c", str[sum%m] );
        }
}