Nhị phân đặc biệt

Một số nguyên dương được gọi là số nhị phân đặc biệt nếu chữ số trong biểu diễn thập phân của nó chỉ gồm chữ số 0 và 1, và nó chứa ít nhất một chữ số 1. Ví dụ: các số \(1\), \(10\), \(11\), \(101\) là số nhị phân đặc biệt, nhưng \(0\), \(22\), \(1002\) thì không.

Cho một số nguyên dương \(n\), hãy tìm bội số nhỏ nhất của \(n\) mà có biểu diễn thập phân là một số nhị phân đặc biệt bắt đầu bằng chữ số \(1\).

Input

Dòng đầu tiên chứa một số nguyên \(K\) — số lượng test (\(1 \le K \le 100\)).

Sau đó là \(K\) dòng, mỗi dòng chứa một số nguyên dương \(n\) (\(1 \le n \le 20000\)).

Output

Với mỗi test, in ra một dòng chứa bội số nhỏ nhất của \(n\) thoả mãn yêu cầu: chỉ gồm các chữ số \(0\) và \(1\), bắt đầu bởi \(1\). Nếu không tồn tại số như trên, in ra \(-1\).

Sample Input 1

3
17
11011
17

Sample Output 1

11101
11011
11101