import sys

digits ="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"

def base2base(number,rBase,sBase):
    '''
    # Implementation of Any base to Decimal, but int() is faster
    dec = 0
    for n in number:
        dec = digits.index(n,0,rBase) + dec * rBase
    '''
    dec = int(number,rBase)
    result = []
    while(dec != 0):
        dec,mod = divmod(dec, sBase)
        result.insert(0,digits[mod])
    for i in result:
        sys.stdout.write( "%s" % (i))
    print


instances = int(raw_input())
for v in range(0,instances):
    data = raw_input().split(" ")
    number = data[0]
    rBase = int(data[1])
    sBase = int(data[2])
    if(number != '0'):
       base2base(number,rBase,sBase)
    #print dec2Base(sBase,int(number,rBase))
    else:
        print 0