Cho số nguyên dương N (0 ≤ N ≤ 10¹⁵).

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.

Dữ liệu: Vào từ file văn bản PRODUCT.INP:

• Dòng thứ nhất ghi số nguyên dương T (2 ≤ T ≤ 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

Kết quả: 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.

Ví dụ

Đề HSG 9 năm học 2014-2015