Prime Factor

Time Limit: 3 sec

**The Problem**

In number theory, the **prime factors** of a positive integer are the prime numbers that divide that integer exactly.The prime factorization of a positive integer is a list of the integer's prime factors, together with their multiplicities; the process of determining these factors is called integer factorization. The fundamental theorem of arithmetic says that every positive integer has a single unique prime factorization.

For example

360 = 2*2*2*3*3*5 = 2^3*3^2*5

In this problem given an integer number **N**, you need to print the prime factorization of this number.

**The Input**

Input begins with an integer **T (1 ≤ T ≤ 100)**, the number of test cases, followed by **T** lines, each line containing an integer **N (2 ≤ N ≤ 10^18)**.

**The Output**

For each test case, you should print a single line, the line contain the prime factorization of the the number **N**. See the sample input and output for more clear understand.

**Sample Input**

4

2

6

72

360

**Sample Output**

2

2*3

2^3*3^2

2^3*3^2*5

Inter University Programming Contest - 2017 [BGC Trust University Bangladesh]

Problem Setter: Shahin ShamS