Cho số tự nhiên ~N~ có thể được biểu diễn dưới dạng ~a^2 \times b~ với ~a, b~ là hai số nguyên tố. Từ số ~N~ được cho, hãy tìm ~a~ và ~b~.

Input

• Dòng đầu tiên chứa số nguyên dương ~T~ là số bộ test (~T \leq 20~).

• ~T~ dòng tiếp theo, mỗi dòng chứa ~1~ số nguyên dương ~N~ miêu tả một bộ test (~N \leq 10^{18}~).

Output

Gồm ~T~ dòng, mỗi dòng chứa ~2~ số nguyên ~a~ ~b~ là câu trả lời cho bộ test tương ứng.

Scoring

• Subtask ~1~ (~30~ điểm): ~N \leq 2 \times 10^9~.

• Subtask ~2~ (~70~ điểm): không có ràng buộc gì thêm.

Sample Input 1

2
604
45

Sample Output 1

2 151
3 5

Notes

~604 = 2^2 \times 151~.

~45 = 3^2 \times 5~.