Prime Factorization with Frequencies

You are given an integer n (where n >= 2). Your task is to compute its prime factorization and output the factors along with their frequencies in the form prime^frequency, separated by a single space.

The prime factorization of an integer n can be expressed in the form:

$$n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$$

For example, if n = 18, its prime factorization is:

$$18 = 2^1 \times 3^2$$

Your program should process multiple test cases. For each test case, output a single line containing the prime factors in increasing order. Each factor and its frequency should be formatted as prime^frequency.

Note: The input is given via standard input (stdin) and the output should be written to standard output (stdout).

inputFormat

The first line of input contains a single integer T representing the number of test cases. Each of the following T lines contains a single integer n (n >= 2) for which the prime factorization is to be computed.

Example:

3
18
28
10

outputFormat

For each test case, output a single line containing the space-separated pairs of prime factors and their frequencies formatted as prime^frequency. The factors should be in increasing order.

Example Output:

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

## sample

3
18
28
10

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

</p>