월요일-토요일

7로 나누었을 때, 나머지가 1 또는 6인 숫자를 7N+{1,6} 숫자라고 한다. 하지만, 발음하기 어려우므로 이러한 숫자를 월요일-토요일 숫자라고 하자.

월요일-토요일 숫자 a와 b가 있을 때, ax = b를 만족하는 월요일-토요일 숫자 x가 있다면, a를 b의 월요일-토요일 약수라고 한다. 사실, 월요일-토요일 숫자 a가 b의 약수(일반적인 약수)라면, a는 b의 월요일-토요일 약수이다. 또, 역도 성립한다.

월요일-토요일 소수란 1보다 큰 월요일-토요일 숫자가 1과 자기 자신을 제외하고 월요일-토요일 약수가 없는 수이다. 월요일-토요일 숫자가 소수일 때, 이 수는 월요일-토요일 소수이다. 하지만, 그 역은 성립하지 않는다. 예를 들어, 27은 월요일-토요일 소수이지만, 소수는 아니다.

어떤 월요일-토요일 숫자의 월요일-토요일 약수 중에서 월요일-토요일 소수인 것을 월요일-토요일 소인수라고 한다. 예를 들어, 27은 216의 월요일-토요일 소인수이다. (216 = 27 * 8)

1보다 큰 월요일-토요일 솟자는 하나 또는 그 이상의 월요일-토요일 소수의 곱으로 나타낼 수 있다. 이러한 표현은 유일하지 않다. 예를 들어, 216 = 6 * 6 * 6 = 8 * 27이다.

월요일-토요일 숫자가 주어졌을 때, 월요일-토요일 소인수를 모두 구하는 프로그램을 작성하시오.

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 월요일-토요일 수가 주어진다. 이 수는 1보다 크고, 300000보다 작다. 입력의 마지막 줄에는 1이 주어진다.

입력으로 주어진 월요일-토요일 숫자에 대해서, 그 숫자를 출력하고, ":"을 출력한 다음에 월요일-토요일 소인수를 오름차순으로 출력한다. 모든 월요일-토요일 소인수 앞에는 공백을 한 칸 출력해야 한다.