Cho \(q\) truy vấn. Mỗi truy vấn cho số \(n\), in ra các thừa số nguyên tố của \(n\) cùng số mũ.

Định dạng đầu vào

• Dòng đầu: \(q\) (\(1 \le q \le 10^5\)).
• \(q\) dòng tiếp: \(n\) (\(2 \le n \le 10^7\)).

Định dạng đầu ra

• Với mỗi truy vấn, in ra các cặp \(p\) (thừa số) và \(a\) (số mũ), cách nhau dấu cách.

Ví dụ

Input:

2
60
7

Output:

2 2 3 1 5 1
7 1

Ràng buộc

• 100% số điểm: \(n \le 10^7\).