Zeros and Ones - 2

Gusagwa, a prince of Poland, likes every number that satisfies all of the following.

• It consists only of the digits 0 and 1.
• It contains at least one 1.
• It does not start with 0.

For example, $101$ is a number Gusagwa likes.

Given a natural number $N$, write a program that finds the smallest number that is a multiple of $N$ and is also a number Gusagwa likes.

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

Each of the next $T$ lines contains one natural number $N$. $N$ is at most 1,000,000.

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