Có \(t\) số \(n_1, n_2, \dots, n_t\), hãy phân tích \(t\) số đấy thành thừa số nguyên tố.

Cụ thể, với số \(n\) bất kỳ, hãy phân tích \(n\) thành thừa số nguyên tố, và sau đó thu gọn lại với nguyên tắc như sau:

• Các thừa số nguyên tố được sắp xếp tăng dần từ trái sang phải
• Nếu thừa số \(p\) xuất hiện \(k>1\) lần, ta thu gọn lại thành \(k^p\).

Vì chúng ta đang in ra màn hình console, nên ta sẽ thay ký tự ^ thay cho phép lũy thừa, và ký tự * thay cho phép nhân.

Ví dụ:

Dữ liệu đầu vào

• Dòng đầu tiên chứa số \(t\) \((t \leq 100000)\)
• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa số \(n_i\) \((2 \leq n_i \leq 10^7)\).

Định dạng đầu ra

• In ra \(n\) dòng, dòng thứ \(i\) in ra phân tích thừa số nguyên tố rút gọn theo quy tắc trên của \(n_i\).

Điểm số

• Subtask \(1\) (\(60\%\) số điểm): \(n_i, t \leq 1000\)
• Subtask \(n\) (\(100\%\) số điểm): không có giới hạn nào khác

Ví dụ

4
2
16
45
95256

2
2^4
3^2*5
2^3*3^5*7^2