월요일-토요일

$7$로 나누었을 때 나머지가 $1$ 또는 $6$인 정수를 $7N + {1, 6}$ 수라고 한다. 하지만 이렇게 부르기는 번거로우므로, 이러한 수를 월요일-토요일 수라고 부르기로 한다.

두 월요일-토요일 수 $a$와 $b$에 대하여, $a x = b$를 만족하는 월요일-토요일 수 $x$가 존재하면 $a$를 $b$의 월요일-토요일 약수라고 한다. 사실 월요일-토요일 수 $a$가 (보통의 의미로) $b$의 약수이면 $a$는 $b$의 월요일-토요일 약수이며, 그 역도 성립한다.

월요일-토요일 소수란 $1$보다 큰 월요일-토요일 수 중에서 $1$과 자기 자신을 제외한 월요일-토요일 약수가 없는 수이다. 월요일-토요일 수가 (보통의 의미로) 소수이면 그 수는 월요일-토요일 소수이지만, 그 역은 성립하지 않는다. 예를 들어 $27$은 월요일-토요일 소수이지만 보통의 소수는 아니다.

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

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

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

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

각 테스트 케이스에 대하여, 입력으로 주어진 월요일-토요일 수를 출력한 뒤 :를 출력하고, 이어서 그 수의 월요일-토요일 소인수를 오름차순으로 출력한다. 각 월요일-토요일 소인수 앞에는 공백을 한 칸씩 출력한다.