Factoring

A prime number (or prime) is an integer greater than 1 whose only positive divisors are 1 and itself. An integer greater than 1 that is not prime is called composite. By the fundamental theorem of arithmetic (the unique factorization theorem), every integer greater than 1 is either prime or a product of primes; although the order of those primes is arbitrary, the multiset of primes itself is unique. Writing the prime factors of a composite number in ascending order therefore yields a unique prime factorization. Given an integer greater than 1, state whether it is prime, or give its unique prime factorization if it is composite.

The first line contains a positive integer $n$, the number of input lines that follow. Each of the next $n$ lines contains one integer greater than 1 and less than $2^{31}$.

For each input line other than the first, print the number followed by a colon, then either prime if the number is prime or its unique prime factorization if it is composite. The primes in the factorization are separated by a single space, and there is a single space after the colon. In other words, each line has the form N: prime or N: p1 p2 ....