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