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.Arrays;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int[] num = new int[85715];
		int[] sosu = new int[35813];
		int[] tansaku = new int[300001];
		for(int i=6;i<=300000;++i){
			if(i%7==6 || i%7==1){
				tansaku[i]=1;
			}
		}
		int end=(int)Math.sqrt((double)300000);
		for(int i=6;i<=end;i++){
			if(tansaku[i]==1){
				for(int j=i+i;j<=300000;j+=i){  // 素数の定数倍は素数とならないので排除するループ
					if(tansaku[j]==1){
						tansaku[j]=0;
					}
				}
			}
		}
		int m=0;
		for(int i=6;i<=300000;++i){
			if(tansaku[i]==1){
				sosu[m]=i;
				++m;
			}
		}
		
		while(true){
			int n = sc.nextInt();
			if(n==1) break;
			Queue<Packet> que = new LinkedList<Packet>();
			HashSet<Integer> ans = new HashSet<Integer>();
			for(int i=0;i<sosu.length;++i){
				if(n%sosu[i]==0)
					if(n/sosu[i]==1) ans.add(sosu[i]);
					else que.add(new Packet(n/sosu[i],sosu[i]));
			}
			while(!que.isEmpty()){
				Packet pa = que.remove();
				for(int i=0;i<sosu.length;++i){
					if(pa.n%sosu[i]==0){
						if(pa.n/sosu[i]==1) ans.addAll(pa.set);
						else que.add(new Packet(pa.n/sosu[i],sosu[i]));
					}
				}
			}
			Iterator iterator = ans.iterator();
			int[] anss = new int[ans.size()];
			System.out.print(n+":");
			for(int i=0;i<ans.size();++i){
				anss[i]=(int) iterator.next();
			}
			Arrays.sort(anss);
			for(int i=0;i<anss.length-1;++i){
				System.out.print(" "+anss[i]);
			}
			System.out.println(" "+anss[anss.length-1]);
		}
	}
	
	public static class Packet{
		int n;
		HashSet<Integer> set = new HashSet<Integer>();
		Packet(int n,int sosu){
			this.n=n;
			set.add(sosu);
		}
	}
}

