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.util.regex.*;
import static java.lang.Math.*;
import static java.lang.System.out;

// AOJ5
public class Main {
	final Scanner sc=new Scanner(System.in);
	final int[] vx={0,1,0,-1}, vy={-1,0,1,0};
	static class Point{
		int x, y;
		Point(int x, int y){	this.x=x;	this.y=y;}
		Point(){	this.x=0; this.y=0;}
		@Override public String toString(){	return "("+this.x+","+this.y+")";}
		static boolean ok(int x,int y,int X,int Y,int min){	return (min<=x&&x<X)&&(min<=y&&y<Y);}
		static boolean ok(int x,int y,int X,int Y){	return ok(x,y,X,Y,0);}
	}
	public static void main(String[] args) {
		new Main().AOJ1154();
	}
	
	void AOJ1154(){
		final int MAX=300000;
		boolean[] list=list(MAX);
		//debug
		//for(int i=6; i<=MAX; i++)	if(list[i])	out.print(" "+i);
		//out.println();
		while(sc.hasNext()){
			int n=sc.nextInt();
			if(n==1)	break;
			out.print(n+":");
			for(int i=6; i<=n; i+=7){
				if(list[i] && n%i==0)	out.print(" "+i);
				if(list[i+2] && n%(i+2)==0)	out.print(" "+(i+2));
			}
			out.println();
		}
	}
	boolean[] list(int MAX){
		boolean[] b=new boolean[MAX+1];
		Arrays.fill(b, false);
		for(int i=6; i<=MAX; i+=7){
			b[i]=true;	b[i+2]=true;
		}
		for(int i=6; i<=MAX; i+=7){
			if(b[i])	for(int j=i+i; j<=MAX; j+=(i))	b[j]=false;
			if(b[i+2])	for(int j=i+i+4; j<=MAX; j+=(i+2))	b[j]=false;
		}
		return b;
	}
	
	void A(){
		while(true){
			int n = sc.nextInt();
			int m = sc.nextInt();
			if(n == 0 && m == 0){
				break;
			}
			int [] taro = new int[n];
			int [] hanako = new int[m];
			int sum1 = 0,sum2 = 0;
			for(int i = 0; i < n; i++){
				taro[i] = sc.nextInt();
				sum1 += taro[i];
			}
			for(int i = 0; i < m ;i++){
				hanako[i] = sc.nextInt();
				sum2 += hanako[i];
			}
			Arrays.sort(taro);
			Arrays.sort(hanako);
			boolean flg = true;
			for(int i =0; i < n ;i++){
				for(int j = 0; j < m; j++){
					int temp1 = sum1 - taro[i] + hanako[j];
					int temp2 = sum2 - hanako[j] + taro[i];
					if(temp1 ==  temp2){
						flg = false;
						System.out.println(taro[i] + " " + hanako[j]);
						break;
					} 
				}
				if(! flg){
					break;
				}
			}
			if(flg){
				System.out.println(-1);
			}
		}
		
	}
}