Numbers are Easy

Interview

Time limit1sMemory limit256 MB

Summary

Find the smallest positive multiple of N whose decimal digits are only 0 and 1 for each test case.

Level: Medium5 of 10
Topics: BFS, Graph, Number theory
Solved: No attempts yet

Problem

You are given an integer $N$ . Find the smallest positive integer $X$ that is divisible by $N$ and whose base 10 representation uses only the digits 0 and 1.

Input

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

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

Output

For each test case, print on its own line the smallest positive integer $X$ that is divisible by $N$ and contains only the digits 0 and 1.

Under these constraints a solution always exists, and it fits in a signed 64 bit integer.

Examples3

Example 1
Input
```
3
1
2
20
```
Expected output
```
1
10
100
```

Example 2

Input

Expected output

Example 3
Input
```
1
1
```
Expected output
```
1
```