Prime Factorisation

Lab C Intermediate 20 points

Print the prime factorisation of each input number as 2^3 * 3 * 5.

Input

n, then n integers ≥ 2.

Output

n lines.

Example

Input

Output

2^3 * 3 * 5
97
2^10
2^3 * 3^2 * 5

Sample input available Sample output available

Editor

Hints

Divide out each factor completely before moving to the next.

Whatever remains above 1 is a prime.

Solution explanation

Every integer has exactly one prime factorisation (the fundamental theorem of arithmetic).

Show solution

#include <stdio.h>

int main() {
    int n, x;
    scanf("%d", &n);
    for (int t = 0; t < n; t++) {
        scanf("%d", &x);
        int first = 1;
        for (int p = 2; p * p <= x; p++) {
            int e = 0;
            while (x % p == 0) {
                x /= p;
                e++;
            }
            if (e > 0) {
                if (!first) printf(" * ");
                if (e == 1) printf("%d", p);
                else printf("%d^%d", p, e);
                first = 0;
            }
        }
        if (x > 1) {
            if (!first) printf(" * ");
            printf("%d", x);
        }
        printf("\n");
    }
    return 0;
}

Output

Answer