Chief Judge's log, stardate 48642.5. We have decided to make a problem from elementary number theory. The problem looks like finding all prime factors of a positive integer, but it is not.

A positive integer whose remainder divided by 7 is either 1 or 6 is called a 7N+{1,6} number. But as it is hard to pronounce, we shall call it a Monday-Saturday number.

For Monday-Saturday numbers a and b, we say a is a Monday-Saturday divisor of b if there exists a Monday-Saturday number x such that ax = b. It is easy to show that for any Monday-Saturday numbers a and b, it holds that a is a Monday-Saturday divisor of b if and only if a is a divisor of b in the usual sense.

We call a Monday-Saturday number a Monday-Saturday prime if it is greater than 1 and has no Monday-Saturday divisors other than itself and 1. A Monday-Saturday number which is a prime in the usual sense is a Monday-Saturday prime but the converse does not always hold. For example, 27 is a Monday-Saturday prime although it is not a prime in the usual sense. We call a Monday-Saturday prime which is a Monday-Saturday divisor of a Monday-Saturday number a a Monday-Saturday prime factor of a. For example, 27 is one of the Monday-Saturday prime factors of 216, since 27 is a Monday-Saturday prime and 216 = 27 × 8 holds.

Any Monday-Saturday number greater than 1 can be expressed as a product of one or more Monday-Saturday primes. The expression is not always unique even if differences in order are ignored. For example,  216 = 6 × 6 × 6 = 8 × 27  holds.

Our contestants should write a program that outputs all Monday-Saturday prime factors of each input Monday-Saturday number.

Input

The input is a sequence of lines each of which contains a single Monday-Saturday number. Each Monday-Saturday number is greater than 1 and less than 300000 (three hundred thousand). The end of the input is indicated by a line containing a single digit 1.

Output

For each input Monday-Saturday number, it should be printed, followed by a colon `:' and the list of its Monday-Saturday prime factors on a single line. Monday-Saturday prime factors should be listed in ascending order and each should be preceded by a space. All the Monday-Saturday prime factors should be printed only once even if they divide the input Monday-Saturday number more than once.

Sample Input


205920
262144
262200
279936
299998
1


Output for the Sample Input


205920: 6 8 13 15 20 22 55 99
262144: 8
262200: 6 8 15 20 50 57 69 76 92 190 230 475 575 874 2185
279936: 6 8 27
299998: 299998






Example

Input

205920
262144
262200
279936
299998
1


Output

205920: 6 8 13 15 20 22 55 99
262144: 8
262200: 6 8 15 20 50 57 69 76 92 190 230 475 575 874 2185
279936: 6 8 27
299998: 299998
import java.util.*;
import java.io.*;
import java.awt.geom.*;
import java.math.*;

public class Main {

	static final Scanner in = new Scanner(System.in);
	static final PrintWriter out = new PrintWriter(System.out,false);
	static boolean debug = false;

	static ArrayList<Integer> ps = new ArrayList<>();
	static final int M = 300001;
	static HashSet<Integer> ans;

	static void init() {
		ArrayList<Integer> list = new ArrayList<>();
		for (int i=6; i<=M; i++) {
			if (i%7 == 1 || i%7 == 6) list.add(i);
		}

		boolean[] f = new boolean[M+1];
		for (int i=0; i<list.size(); i++) {
			f[list.get(i)] = true;
		}

		for (int i=6; i<=M; i++) {
			if (!f[i]) continue;
			ps.add(i);
			for (int j=i+i; j<M; j+=i) {
				f[j] = false;
			}
		}

		// dump(ps);
	}

	static boolean rec(int n) {
		if (n == 1) return true;
		boolean f = false;
		for (int i=0; i<ps.size(); i++) {
			if (n%ps.get(i) == 0) {
				if (rec(n/ps.get(i))) {
					ans.add(ps.get(i));
					f = true;
				}
			}
		}
		return f;
	}

	static boolean solve() {
		int n = in.nextInt();
		if (n == 1) return false;

		// dump(ps);

		ans = new HashSet<Integer>();
		rec(n);
		ArrayList<Integer> list = new ArrayList<>(ans);
		Collections.sort(list);
		out.print(n+":");
		for (int i=0; i<list.size(); i++) {
			out.print(" "+list.get(i));
		}
		out.println();
		// dump(ans);

		return true;
	}

	public static void main(String[] args) {
		debug = args.length > 0;
		long start = System.nanoTime();

		init();
		while(solve());
		out.flush();

		long end = System.nanoTime();
		dump((end - start) / 1000000 + " ms");
		in.close();
		out.close();
	}

	static void dump(Object... o) { if (debug) System.err.println(Arrays.deepToString(o)); }
}