Cho ~q~ câu hỏi, mỗi câu hỏi cho một số nguyên ~x~ (~x \ge 2~). Hãy phân tích ~x~ thành tích các thừa số nguyên tố.

Input:

• Dòng thứ nhất chứa số nguyên ~q~.
• ~q~ dòng tiếp theo, mỗi dòng chứa một số nguyên ~x~.

Output:

Gồm ~q~ dòng. Dòng thứ ~i~ ghi các cặp ~p~ và ~e~ theo thứ tự ~p~ tăng dần, trong đó ~p~ là thừa số nguyên tố và ~e~ là số mũ tương ứng. Các số cách nhau bởi dấu cách.

Ràng buộc:

~1 \le q \le 10^5~, ~2 \le x \le 10^{12}~.

• Subtask 1 (20% số điểm): ~q \le 100~, ~x \le 10^4~.
• Subtask 2 (40% số điểm): ~q \le 10^5~, ~x \le 10^6~.
• Subtask 3 (40% số điểm): ~q \le 200~, ~x \le 10^{12}~.

Ví dụ:

Input

3
360
97
1024

Output

2 3 3 2 5 1
97 1
2 10

Giải thích: ~360 = 2^3 \times 3^2 \times 5^1~ nên in ra 2 3 3 2 5 1.