Zeros and Ones

Call a positive integer a good number if it satisfies all of the following.

• In base ten it uses only the digits 0 and 1.
• It contains at least one 1.
• It does not start with 0.
• It has at most 100 digits.

For example, 101 is a good number.

Given a positive integer $N$, write a program that finds the smallest good number that is a multiple of $N$.

The first line contains the number of test cases $T$ ($T < 10$).

Each of the next $T$ lines contains one positive integer $N$ ($1 \le N \le 20000$).

For each test case, print on its own line the smallest good number that is a multiple of $N$. If no such number exists, print BRAK.