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

aW1wb3J0IHN5cwoKZGlnaXRzID0iMDEyMzQ1Njc4OUFCQ0RFRkdISUpLTE1OT1BRUlNUVVZXWFlaIgoKZGVmIGJhc2UyYmFzZShudW1iZXIsckJhc2Usc0Jhc2UpOgogICAgJycnCiAgICAjIEltcGxlbWVudGF0aW9uIG9mIEFueSBiYXNlIHRvIERlY2ltYWwsIGJ1dCBpbnQoKSBpcyBmYXN0ZXIKICAgIGRlYyA9IDAKICAgIGZvciBuIGluIG51bWJlcjoKICAgICAgICBkZWMgPSBkaWdpdHMuaW5kZXgobiwwLHJCYXNlKSArIGRlYyAqIHJCYXNlCiAgICAnJycKICAgIGRlYyA9IGludChudW1iZXIsckJhc2UpCiAgICByZXN1bHQgPSBbXQogICAgd2hpbGUoZGVjICE9IDApOgogICAgICAgIGRlYyxtb2QgPSBkaXZtb2QoZGVjLCBzQmFzZSkKICAgICAgICByZXN1bHQuaW5zZXJ0KDAsZGlnaXRzW21vZF0pCiAgICBmb3IgaSBpbiByZXN1bHQ6CiAgICAgICAgc3lzLnN0ZG91dC53cml0ZSggIiVzIiAlIChpKSkKICAgIHByaW50CgoKaW5zdGFuY2VzID0gaW50KHJhd19pbnB1dCgpKQpmb3IgdiBpbiByYW5nZSgwLGluc3RhbmNlcyk6CiAgICBkYXRhID0gcmF3X2lucHV0KCkuc3BsaXQoIiAiKQogICAgbnVtYmVyID0gZGF0YVswXQogICAgckJhc2UgPSBpbnQoZGF0YVsxXSkKICAgIHNCYXNlID0gaW50KGRhdGFbMl0pCiAgICBpZihudW1iZXIgIT0gJzAnKToKICAgICAgIGJhc2UyYmFzZShudW1iZXIsckJhc2Usc0Jhc2UpCiAgICAjcHJpbnQgZGVjMkJhc2Uoc0Jhc2UsaW50KG51bWJlcixyQmFzZSkpCiAgICBlbHNlOgogICAgICAgIHByaW50IDA=

NAo1NjM3OCAxMCAyCkFCOThCQyAxNSAxMApBQkNERUYxMjM0NTYgMzYgMgoxMDAwMTAwMTAxMDEwIDIgMTA=

4
56378 10 2
AB98BC 15 10
ABCDEF123456 36 2
1000100101010 2 10