Xuất phát là học sinh chuyên toán nên HienJeony chưa bao giờ thấy toán là khó. Trong một tiết học nọ cũng như bao tiết học khác, HienJeony không chú ý nghe giảng nên bị thầy mời trả lời một số câu hỏi vô cùng khó ở bài học mới như sau: Cho biểu thức có phép Logarit là ~log_a(b^x)~ với ~a~ là số nguyên tố, hãy biểu diễn kết quả của phép tính này dưới dạng thừa số nguyên tố.

Input

• Dòng đầu tiên gồm số nguyên dương ~t~ ~(1 \leq t \leq 50)~
• ~t~ tiếp theo, mỗi dòng chứa ~3~ số ~a, b, x~ ~(1 \leq a \leq 10^3, 1 \leq b \leq 10^{18}, 1 \leq x \leq 10^6, a \leq b)~

Output

Trong trường hợp không thể biểu diễn kết quả dưới dạng thừa số nguyên tố thì in ra ~-1~, ngược lại ta in như sau:

• Dòng đầu tiên là các số mũ khi biểu diễn kết quả phép tính dưới dạng thừa số nguyên tố
• Dòng thứ hai là các thừa số nguyên tố khi biểu diễn phép tính

Lưu ý: thứ tự in ra của các số thuộc dòng đầu tiên và dòng thứ hai phải được in sắp xếp tăng dần theo thừa số nguyên tố.

Sample Input

2
3 6 1
3 9 12

Sample Output

-1
3 1 
2 3 

Note

Ở test ví dụ thứ hai, thực hiện phép tính và biểu diễn kết quả dưới dạng thừa số nguyên tố thì ta có: ~log_3(9^{12}) = 24 = 2^3 \times 3^1~