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 static java.lang.Math.*;
public class Main {
	final Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		new Main().init();
	}
	void init(){
		new AOJ1154();
	}
	
	class AOJ1154{
		AOJ1154(){
			prime=sieve(300000);
			while(true){
				int n=sc.nextInt();
				if(n==1)	break;
				solve(n);
			}
		}
		boolean[] prime;
		void solve(int n){
			StringBuilder sb=new StringBuilder(n+":");
			for(int i=6; i<=n; i+=5){
				if(n%i==0 && prime[i])sb.append(" "+i);
				i+=2;
				if(n%i==0 && prime[i])sb.append(" "+i);
			}
			System.out.println(sb);
		}
		boolean[] sieve(int MAX){
			boolean[] list = new boolean[MAX+1];
			for(int i=6; i<=MAX; ++i)list[i]=true;
			for(int i=6; i<=MAX; i+=5) {
				if(list[i])for(int j=i+i; j<=MAX; j+=i)	list[j] = false;
				i+=2;
				if(list[i])for(int j=i+i; j<=MAX; j+=i)	list[j] = false;
			}
			return list;
		}
	}
	
	class AOJ1156{
		AOJ1156(){
			while(true){
				int w=sc.nextInt(),h=sc.nextInt();
				if((w|h)==0)	break;
				solve(w,h);
			}
		}
		final int INF=Integer.MAX_VALUE/4;
		void solve(int w,int h){
			int[][] b=new int[w][h];
			for(int y=0; y<h; ++y)for(int x=0; x<w; ++x)b[x][y]=sc.nextInt();
			int[] c={sc.nextInt(),sc.nextInt(),sc.nextInt(),sc.nextInt()};
			
//			LinkedList<State> open=new LinkedList<State>();
			PriorityQueue<State> open=new PriorityQueue<State>();
			open.add(new State(0,0,1,0));
			
			int[][][] closed=new int[w][h][4];
			for(int i=0; i<w; ++i)for(int j=0; j<h; ++j)for(int k=0; k<4; ++k)closed[i][j][k]=INF;
			closed[0][0][1]=0;
			
			final int[] vx={0,1,0,-1}, vy={-1,0,1,0};
			
			while(!open.isEmpty()){
				State now=open.poll();
//				System.out.println(now);
				if(now.x==w-1 && now.y==h-1){
					System.out.println(now.c);
					break;
				}
				
				for(int v=0; v<4; ++v){
					int tmp=(now.z+v)%4;
					int xx=now.x+vx[tmp];
					int yy=now.y+vy[tmp];
					if(0<=xx&&xx<w && 0<=yy&&yy<h){
						int nc=now.c + (b[now.x][now.y]==v?0:c[v]);
						if(closed[xx][yy][tmp]>nc){
							open.add(new State(xx,yy,tmp,nc));
							closed[xx][yy][tmp]=nc;
						}
					}
				}
			}
		}
		class State implements Comparable<State>{
			int x,y,z,c;
			State(int x,int y,int z,int c){
				this.x=x;
				this.y=y;
				this.z=z;
				this.c=c;
			}
			@Override public int compareTo(State o){
				return this.c-o.c;
			}
			@Override public String toString(){
				return x+","+y+" "+z+" "+c;
			}
		}
	}
	
	class AOJ1155{
		AOJ1155(){
			while(true){
				String str=sc.next();
				if(str.equals("."))	break;
				solve(str);
			}
		}
		void solve(String str){
			int cnt=0;
			str+="#";
			for(int p=0; p<=2; ++p)for(int q=0; q<=2; ++q)for(int r=0; r<=2; ++r){
				String tmp=str.replaceAll("P", ""+p).replaceAll("Q", ""+q).replaceAll("R", ""+r);
//				System.out.println(tmp);
				this.line=tmp.toCharArray();
				this.pos=0;
				int ret=expr();
//				System.out.println(ret);
				cnt += (ret==2?1:0);
			}
			System.out.println(cnt);
		}
		final int[][]	and={{0,0,0},{0,1,1},{0,1,2}},
				or={{0,1,2},{1,1,2},{2,2,2}};
		final int[] m={2,1,0};
		char[] line;
		int pos=0;
		private int expr(){
			int ret=term();
			while(true){
				char op=line[pos];
				if( op=='+' ){
					int old=ret;
					++pos;
					ret=term();
					ret=or[old][ret];
//					System.out.println(old+"+"+ret+" = "+or[old][ret]);
				}else	break;
			}
			return ret;
		}
		private int term(){
			int ret=fact();
			while(true){
				char op=line[pos];
				if( op=='*' ){
					int old=ret;
					++pos;
					ret=fact();
					ret=and[old][ret];
//					System.out.println(old+"*"+ret+" = "+and[old][ret]);
				}else	break;
			}
			return ret;
		}
		private int fact(){
			if(line[pos]=='-'){
				++pos;
				return m[fact()];
			}else if(Character.isDigit(line[pos])){
				int ret=line[pos]-'0';
				++pos;
				return ret;
			}else if(line[pos]=='('){
				++pos;
				int ret=expr();
				++pos;	// ")"テ」ツ?古ヲツ敖・テ」ツつ凝」ツ?ィテ、ツサツョテ・ツョツ?
				return ret;
			}
			return 0;
		}
	}
	
	class AOJ1153{
		AOJ1153(){
			while(true){
				int n=sc.nextInt(),m=sc.nextInt();
				if((n|m)==0)	break;
				solve(n,m);
			}
		}
		void solve(int n,int m){
			int[] nn=new int[n],
					mm=new int[m];
			int ns=0, ms=0;
			for(int i=0; i<n; ++i){
				nn[i]=sc.nextInt();
				ns+=nn[i];
			}
			for(int i=0; i<m; ++i){
				mm[i]=sc.nextInt();
				ms+=mm[i];
			}
			Arrays.sort(nn);
			Arrays.sort(mm);
			int cand1=-1,cand2=-1,sum=Integer.MAX_VALUE/4;
			for(int i=0; i<n; ++i){
				for(int j=0; j<m; ++j){
					if(ns-nn[i]+mm[j] == ms-mm[j]+nn[i] && sum>nn[i]+mm[j]){
						cand1=i;
						cand2=j;
						sum=nn[i]+mm[j];
					}
				}
			}
			System.out.println(cand1<0? "-1" : nn[cand1]+" "+mm[cand2]);
		}
	}
}