import sys

sys.stdin = open('이진수.txt')

T = int(input())

for tc in range(1,1+T):
    N, hexa = input().split()
    # print(hexa)
    tem = []

    for i in hexa:
        if '0' <= i <= '9':
            tem.append(ord(i) - ord('0'))
        else:
            tem.append(ord(i) - ord('A') + 10)
    binary = []

    for j in tem:
        a = int(j)
        imsi = []
        while a > 0:
            b = a % 2
            a //= 2
            imsi.insert(0, b)
        while len(imsi) < 4:
            imsi.insert(0, 0)
        binary += imsi

    print('#{}' .format(tc), end = ' ')

    for z in binary:
        print(z, end = '')
    print()