Factoring

A prime number (or a prime) is an integer greater than 1 that has no positive divisors other than 1 and itself. An integer greater than one that is not prime is called composite. The fundamental theorem of arithmetic, also called the unique factorization theorem or the unique-primefactorization theorem, states that every integer greater than 1 is either prime or is the product of prime numbers, and that, although the order of the primes in the second case is arbitrary, the primes themselves are not. If we place the prime factors of a composite number in ascending order, then we have a unique prime factorization. Given an integer greater than one either state that the integer is prime or give the unique prime factorization of the composite number.

The first line will be a positive integer, n, indicating the number of input lines that follow. Each input line will contain one integer greater than 1 and less than 231.

For each line of input, other than the first, print the number followed by a colon and either the statement that the number is prime or the unique prime factorization of the composite number. Primes in the unique factorization must be separated by a single blank space, and there must be one blank space after the colon.