/*
1147. 进制转换
Time limit per test: 2.0 seconds

Memory limit: 256 megabytes

输入一个十进制数 N，将它转换成 R 进制数输出。

Input
输入一个正整数 T。表示测试数据的组数。

每个测试实例包含两个整数 N(32 位整数) 和 R （2<=R<=36).

Output
为每个测试实例输出转换后的数，每个输出占一行。如果 R 大于 10，则对应的数字规则参考 16 进制（比如，10 用 A 表示 ,16 用 G 表示等等）。

Examples
input
3
7 2
23 12
-4 3
output
111
1B
-11
*/

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

// 定义大数结构
struct Big
{
    int data[200];  //保存每一位，[0]是最低位
    int len;    // 数字位数
    int rad;    // 进制
    int sign;   // 符号，1，0，-1 分别表示 正数，0，负数
};


/* 由字符串生成大数
 * 参数：big 指向大数的指针，用于保存转换结果，前提是先设置正确的进制 big->rad
 *        str 字符串
 */
int strtobig(struct Big *big, char str[])
{
    int len = strlen(str), i;
    char *p = str;

    // 判断是否为负数
    if (*p=='-')
    {
        big->sign = -1;
        p++;
        big->len = len-1;
    } else
    {
        big->sign =1;
        big->len = len;
    }

    // 判断是否为0
    if (big->len==1 && *p=='0')
    {
        big->data[0]=0;
        big->sign = 0;
        return 0;
    }

    // 逐位转换
    for (i=0; i<big->len; i++)
    {
        if (*p>='A')
            big->data[big->len-1-i] = *p - 'A' + 10;
        else
            big->data[big->len-1-i] = *p - '0';
        p++;
    }
    return 0;
}


/* 判断大数是否为0
 * 参数：big 指向大数的指针
 * 返回值：1-大数是0， 0-大数不是0
 */
int iszero(struct Big *big)
{
    if (big->len==1 && big->data[0]==0)
        return 1;
    else
        return 0;
}

/* 大数除法
 * 参数：big 指向大数的指针（被除数），计算完成后，保存商
       n: 除数
 * 返回值：余数
 */
int bigdivn(struct Big *big, int n)
{
    int mod=0;
    for (int i=big->len-1; i>=0; i--)
    {

        mod = big->data[i] + mod * big->rad;
        big->data[i] = mod / n;
        mod = mod % n;
    }
    while (big->len >1 && big->data[big->len-1]==0)
        big->len --;
    return mod;
}

/* 大数转换为字符串
 * 参数：big 指向大数的指针，需要转换的数
 *        str 字符串
 */
int bigtostr(char str[], struct Big *big)
{
    char *radstr="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";

    if (iszero(big))
    {
        str[0] = '0';
        str[1] ='\0';
        return 0;
    }
    int i=0;
    if (big->sign == -1)
        str[i++]='-';
    for (int j=big->len-1; j>=0; j--)
    {
        str[i++] = radstr[big->data[j]];
    }

    str[i]='\0';
    return 0;
}

/* 进制转换
 * 参数：dec: 源数
 *      r: 转换后的数，要求提前设置好r->rad
 */
int dector(struct Big *r, struct Big *dec)
{
    struct Big tmp;
    memcpy(&tmp, dec, sizeof(struct Big));

    if (iszero(dec))
    {
        r->sign = 0;
        r->data[0] = 0;
        r->len = 1;
        return 0;
    }
    r->sign = dec->sign;
    int i=0;
    while (!iszero(&tmp))
    {
       r->data[i++]=bigdivn(&tmp, r->rad);
    }
    r->len = i;
    return 0;
}

/* 打印大数，用于调试
 * 参数：big:大数
 */
int prtbig(struct Big *big)
{
    printf("big sign:%d\n", big->sign);
    printf("big len:%d\n", big->len);
    printf("big rad:%d\n", big->rad);
    printf("big data:");
    for (int i=0;i<big->len;i++)
        printf("%d,", big->data[i]);
    printf("\n");
    return 0;
}


int main()
{
    struct Big dec, r;
    char str[200];
    int qnum;   //问题数
    int rad;

    scanf("%d", &qnum);

    for (int i=0; i<qnum; i++)
    {
        scanf("%s%d", str, &rad);
        dec.rad = 10;
        strtobig(&dec, str);
        r.rad = rad;
        dector(&r, &dec);
        bigtostr(str, &r);
        printf("%s\n", str);
    }
    return 0;
}