• Cho số tự nhiên ~N~, hãy tìm số nguyên dương nhỏ nhất lớn hơn ~0~ mà tích các chữ số của số đó bằng ~N~.

Input

Dòng đầu tiên ghi số nguyên dương ~T~ là số bộ test;

~T~ dòng tiếp theo, mỗi dòng ghi ~1~ số nguyên dương ~N~.

Giới hạn:

• ~(1 \le T \le 100)~,
• ~(1 \le N \le 600)~.

Output

Với mỗi bộ test, ghi ~1~ số nguyên dương là kết quả của bài toán nếu không tìm được số thõa mãn thì in ra ~-1~.

Sample

Input #1

2
12
19

Output #1

26
-1