#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <cstring>
#include <string>
#include <queue>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //n이 1일수도있음...
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        //이문제포인트: n의 나머지는 0부터 n-1까지이다.
        
        //몇에서 해당값이 만들어졌는지
        vector<int> from(n,-1);
        //0추가인지 1추가인지
        vector<int> how(n,-1);
        //나머지값 체크겸 몇번만에 도달하는지
        vector<int> chk(n,-1);
        queue<int> q;
        q.push(1%n);
        chk[1%n]=0;
        how[1%n]=1;
        while(!q.empty()){
            int now=q.front();
            q.pop();
            if(now==0)
                break;
            for(int i=0;i<=1;i++){
                int next=(now*10+i)%n;
                if(chk[next]==-1){
                    chk[next]=chk[now]+1;
                    from[next]=now;
                    how[next]=i;
                    q.push(next);
                }
            }
        }
        //chk[0]이 -1이면 못찾은거임.
        if(chk[0]==-1){
            cout<<"BRAK"<<'\n';
        }else{
            //거꾸로 추적하면 원하는값 찾을수있다.
            string ans="";
            //from[1]==-1이다
            for(int i=0;i!=-1;i=from[i]){
                ans+=to_string(how[i]);
            }
            reverse(ans.begin(),ans.end());
            cout<<ans<<'\n';
        }
    }
    return 0;
}