Mọi số nguyên dương lớn hơn ~1~ đều có thể được phân tích thành tích của các thừa số nguyên tố.

• Ví dụ, số ~20~ có thể được biểu diễn dưới dạng ~2~ ~2~ ~5~ (tức ~20 = 2 × 2 × 5~).

Nhiệm vụ của bạn là thực hiện phân tích này cho ~T~ câu truy vấn.

• Với mỗi câu truy vấn, bạn được cho một số nguyên dương ~N~.
• Bạn cần phân tích ~N~ thành các thừa số nguyên tố và in ra kết quả, trong đó các thừa số được in cách nhau bởi dấu cách.

Input

• Dòng ~1~: Số nguyên ~T~ (số lượng câu truy vấn, ~T < 10^5~).
• ~T~ dòng sau: Mỗi dòng chứa một số nguyên dương ~N~ ~(1 < N < 10^6)~.

Output

• Gồm ~T~ dòng, mỗi dòng là kết quả phân tích thừa số nguyên tố của ~N~, các thừa số cách nhau bởi dấu cách.

Sample Input

2
10
40

Sample Output

2 5
2 2 2 5