Số nguyên tố luôn mang đến cho Tom nhiều điều thích thú. Lần này Thầy giao cho Tom một bài toán tưởng chừng như rất dễ nhưng lại đem đến cho Tom một thử thách mới. Bài toán như sau:

Cho bạn một số nguyên dương \(T\) là số test cần xử lý. \(T\) dòng tiếp theo là \(T\) số nguyên dương \(M\), hãy phân tích \(M\) ra thành tích các thừa số nguyên tố.

Đây là một bài toán khá đơn giản. Tuy nhiên, Thầy đã ra cho Minh một giới hạn là \(T \le 10^5\) và \(M \le 10^7\).

Em hãy giúp Minh vượt qua thử thách này nhé.

Input

• Dòng đầu tiên chứa số lượng các test \(T\).
• \(T\) dòng tiếp theo, mỗi dòng chứa số nguyên dương \(M\).

Output

• Xuất ra \(T\) chuỗi là tích các thừa số nguyên tố nằm trên \(T\) dòng trả lời cho \(T\) test ở trên.

Constraints

• \(T \le 10^5\)
• \(M \le 10^7\)

Example

2
15
30

3*5
2*3*5