白俊8111号0と1.

from collections import deque
t = int(input())

def bfs(n):
    u = 10 % n
    q = deque()
    q.append((1, 1))
    while q:
        x, mod = q.popleft()
        if x >= 10 ** 101:
            print('BRAK')
            return
        for y in [10 * x + 1, 10 * x]:
            if y % n == 0:
                print(y)
                return
            if y == 10 * x + 1:
                q.append((y, (mod * u + 1) % n))
            if y == 10 * x:
                q.append((y, (mod * u ) % n)) 
    
for _ in range(t):
    n = int(input())
    bfs(n) 

from collections import deque

def bfs(n):
    check = [-1] * n
    how = [-1] * n
    afrom = [-1] * n
    
    q = deque()
    q.append(1 % n)
    check[1 % n] = 0
    how[1 % n] = 1
    while q:
        x = q.popleft()
        for y in [10 * x, (10 * x) + 1]:
            if check[y % n] == -1:
                if y == 10 * x:
                    how[y % n] = 0
                else:
                    how[y % n] = 1
                afrom[y % n] = x
                q.append(y % n)
                check[y % n] = check[x] + 1
                
    ans = []
    if check[0] == -1:
        print('BRAK')
    else:
        i = 0
        while i != -1:
            ans.append(how[i])
            i = afrom[i]
    print(*ans[::-1], sep = '')
    
t = int(input())

for _ in range(t):
    n = int(input())
    bfs(n)