/*
ACMプログラミングコンテスト 過去問 2008年国内予選 Problem B

■月曜土曜素因数

審判長日誌，宇宙暦 48642.5．われわれは，初等整数論から出題することに決めた．正整数の素因数をすべて求めることに似た問題だが，そうではない． 

7 で割った余りが 1 または 6 である正整数は 7N+{1,6} 数と呼ばれる．しかし，発音しにくいので， 月曜土曜数と呼ぼう． 

月曜土曜数 a, b に対して，月曜土曜数 x が存在して ax = b が成り立つとき， a を b の月曜土曜約数と呼ぶ．月曜土曜数 a が月曜土曜数 b の月曜土曜約数であるためには， a が b の普通の意味の約数であれば必要十分であると，簡単に証明できる． 

1 より大きな月曜土曜数でそれ自身と 1 の他に月曜土曜約数をもたないものを， 月曜土曜素数と呼ぶ．普通の意味の素数である月曜土曜数は月曜土曜素数であるが，逆は一般に成り立たない．たとえば，27 は普通の意味の素数ではないが，月曜土曜素数である．月曜土曜数 a の月曜土曜約数である月曜土曜素数を， a の月曜土曜素因数と呼ぶ．たとえば， 27 は月曜土曜素数であり， 216 = 27 × 8 が成り立つので， 27 は 216 の月曜土曜素因数のひとつである． 

1 より大きなどんな月曜土曜数も， 1 個以上の月曜土曜素数の積として表すことができる．表し方は，順序の違いを無視しても，必ずしも一通りではない．たとえば， 216 = 6 × 6 × 6 = 8 × 27 である． 

選手は，入力された各々の月曜土曜数に対して，その月曜土曜素因数をすべて出力するプログラムを書かなくてはならない． 

Input
入力は行の並びで，各行に一つの月曜土曜数が含まれている．各々の月曜土曜数は 1 より大きく 300000 （三十万）より小さい．入力の終わりは，数字 1 が 1 文字だけ含まれる行で示される． 


Output
入力された月曜土曜数それぞれに対して，その数が表示され，つづけて同じ行に，コロン「:」，そして，月曜土曜素因数の並びがそれぞれの前に空白を置いて小さい順に出力されなくてはならない．各月曜土曜素因数は，たとえ入力された月曜土曜数を 2 回以上割るものであっても，ちょうど 1 回だけ出力されなくてはならない． 


■解答例

整数のあるサブセットからなる世界の中を「月曜土曜数」と読むと、この問題は、そのサブセットにおける素数の列挙の問題に帰着される。おそらくもっと効率的な解き方があるだろうが、最も単純に問題を解くには、月曜土曜数となる数字からその世界での素数を列挙し、問題で与えられる数値を割ることのできる素数をすべてプリントすればよい。

整数から月曜土曜数への写像は以下のようにして与えられる。

7*0+1 = 1			(0)
7*0+6 = 6			(1)
7*1+1 = 8			(2)
7*1+6 = 13		(3)
7*2+1 = 15		(4)
7*2+6 = 20		(5)

value = (n/2)*7 + (n%2==0?1:6);

この問題は、「素因数分解」ではないため、関数の再帰などは必要ない。問題で与えられる数値を割り切れることのできる素数を列挙するのみであるため、月曜土曜数の中での素数一覧を作ることができれば、あとは一回その一覧をループする制御文を作成するだけでよい。

*/
import java.io.*;
import java.util.*;

public class Exp2008_B {
	/** 月曜土曜素数であるかを調べる。 */
	public static boolean isPrime(int value){
		for(int cnt=1;num(cnt)<value;cnt++){
			if(value%num(cnt)==0){
				return false;
			}
		}
		return true;
	}
	/** 整数から月曜土曜数へ写像する。 */
	public static int num(int index){
		return (index/2)*7+(index%2==0?1:6);
	}
	/**　メイン関数 */
	public static void main(String[] args) throws Exception{
		Vector<Integer> primes = new Vector<Integer>();
		for(int cnt=1;num(cnt)<=300000;cnt++){
			if(isPrime(num(cnt))){
				primes.add(new Integer(num(cnt)));
			}
		}

		BufferedReader br = new BufferedReader(new FileReader(args[0]));
		PrintWriter pw = new PrintWriter(new FileWriter(args[1]));

		while(true){
			String line = br.readLine();
			if(line.equals("1")){
				break;
			}
			int value = Integer.parseInt(line);
			Vector<Integer> numbers = new Vector<Integer>();
			for(Integer p : primes){
				if(value%p.intValue()==0){
					numbers.add(p);
				}
			}

			pw.print(value+":");
			for(Integer v : numbers){
				pw.print(" "+v);
			}
			pw.print("\n");
		}

		br.close();
		pw.close();
	}
}