소인수분해

소수(prime)는 1보다 큰 정수 중에서 1과 자기 자신 외에는 양의 약수를 가지지 않는 수이다. 1보다 크면서 소수가 아닌 정수는 합성수(composite)라고 한다. 산술의 기본 정리(소인수분해의 유일성 정리)에 따르면, 1보다 큰 모든 정수는 소수이거나 소수들의 곱으로 나타낼 수 있으며, 곱하는 순서를 무시하면 그 소인수의 구성 자체는 유일하게 결정된다. 따라서 합성수의 소인수를 오름차순으로 나열하면 유일한 소인수분해를 얻는다. 1보다 큰 정수가 주어질 때, 그 수가 소수인지 판별하고 합성수라면 유일한 소인수분해를 출력하여라.

첫째 줄에는 이어지는 입력 줄의 개수를 나타내는 양의 정수 $n$이 주어진다. 그 다음 $n$개의 줄에는 각각 1보다 크고 $2^{31}$보다 작은 정수가 하나씩 주어진다.

첫째 줄을 제외한 각 입력 줄에 대해, 해당 정수를 출력한 뒤 콜론(:)을 붙인다. 그 수가 소수이면 prime을 출력하고, 합성수이면 유일한 소인수분해를 출력한다. 소인수분해에서 각 소인수는 하나의 공백으로 구분하며, 콜론 뒤에도 공백이 하나 있어야 한다. 즉 각 줄은 N: prime 또는 N: p1 p2 ... 형식이다.