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