Cho số nguyên dương $N$ $(0\le N\le {10}^{15})$.

Yêu cầu

Tìm số nguyên dương $Q$ nhỏ nhất sao cho tích các chữ số của $Q$ bằng $N$.

Input

Vào từ file văn bản PRODUCT.INP:

• Dòng thứ nhất ghi số nguyên dương $T$ $(2\le T\le 100)$ là số lượng test.
• $T$ dòng tiếp theo, mỗi dòng ghi một số nguyên dương $N$

Output

Ghi ra file văn bản PRODUCT.OUT gồm $T$ dòng, mỗi dòng ghi ra số $Q$ tìm được tương ứng với số $N$, nếu không tìm được thì ghi ra số $-1$.

Scoring

• Không có giới hạn gì thêm

Ví dụ

Input

3
10
16
13

Output

25
28
-1