Bedao Mini Contest 07 - LOGA

View as PDF

Submit solution


Points: 0.20 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
C, C++, Java, Pascal, Python

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~


Comments

Please read the guidelines before commenting.


There are no comments at the moment.