Với số nguyên dương ~K~ cho trước, số nguyên dương ~N~ được gọi là "số đẹp" nếu tổng các chữ số của ~N~ cũng như tổng chữ số của ~N~ ~+~ ~1~ khi viết trong hệ thập phân thì đều chia hết cho ~K~.

Yêu cầu: Cho ~Q~ câu hỏi, mỗi câu gồm một số nguyên dương ~K~. Viết chương trình tìm số đẹp nhỏ nhất ứng với mỗi số ~K~. Biết rằng giá trị số đẹp như thế có thể rất lớn và thậm chí không tồn tại.

Input

Vào từ file SODEP.INP:

• Dòng 1: gồm một số nguyên ~Q~ (~1 \le Q \le 10~) là số lượng số ~K~;

• Trong ~Q~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~K~ (~K \le 10^{12}~).

Output

Ghi ra file SODEP.OUT gồm ~Q~ dòng, mỗi dòng ứng với mỗi ~K~ trong dữ liệu vào. Nếu tìm được số đẹp thì in ra hai số nguyên: chữ số đầu tiên từ trái qua và tổng chữ số của nó; trong trường hợp không tồn tại số đẹp thì in ra ~-1~.

Scoring

Sample Input 1

3
2
2025
10

Sample Output 1

1 10
-1
1 90

Notes

• Với ~K = 2~, số ~N = 19~ là số đẹp nhỏ nhất vì khi đó ~N~ ~+~ ~1~ ~=~ ~20~ và ~N~, ~N~ ~+~ ~1~ có tổng chữ số lần lượt là ~10~, ~2~ đều chia hết cho ~2~.

• Với ~K = 2025~ không tồn tại số đẹp ~N~.

• Với ~K = 10~ thì ~N = 18999999999~ có tổng chữ số là ~90~ và ~N~ ~+~ ~1~ ~=~ ~19000000000~ có tổng chữ số là ~10~; các tổng này đều chia hết cho ~10~.