Đề bài

Cho nhiều truy vấn, mỗi truy vấn gồm một số nguyên dương x.

Hãy phân tích x thành tích các thừa số nguyên tố.

Các thừa số phải được in theo thứ tự tăng dần của số nguyên tố.

Dữ liệu vào

Dòng đầu chứa số nguyên Q.

Q dòng tiếp theo, mỗi dòng chứa một số nguyên x.

Dữ liệu ra

Với mỗi truy vấn, in các cặp:

p^e

trong đó p là thừa số nguyên tố và e là số mũ của p.

Giới hạn

1 ≤ Q ≤ 10⁵
1 ≤ x ≤ 10⁶

Ví dụ

Input

3
60
84
97

Output

2^2 3^1 5^1
2^2 3^1 7^1
97^1