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.math.BigDecimal;
import java.awt.geom.*;
import static java.util.Arrays.*;
import static java.lang.Math.*;

public class Main{

    static final Reader sc = new Reader();
    static final PrintWriter out = new PrintWriter(System.out,false);

    public static void main(String[] args) throws Exception {
        ArrayList<Integer> list = new ArrayList<Integer>();
        int count = 0;
        for(int i=1;i*7<300000;i++){
        	list.add(7*i-1);
        	count++;
        	for(int j=0;j<list.size()-1;j++){
        		int x = list.get(j);
        		if((7*i-1)%x==0){
        			list.remove(count-1);
        			count--;
        			break;
        		}
        	}
        	list.add(7*i+1);
        	count++;
        	for(int j=0;j<list.size()-1;j++){
        		int x = list.get(j);
        		if((7*i+1)%x==0){
        			list.remove(count-1);
        			count--;
        			break;
        		}
        	}
        }
        while(true){
        	int n = sc.nextInt();
        	if(n==1){
        		break;
        	}
        	out.print(n+":");
        	for(int i=0;i<list.size();i++){
        		int x = list.get(i);
        		if(n%x==0){
        			out.print(" "+x);
        		}
        	}
        	out.println();
        	out.flush();
        }
        sc.close();
        out.close();
    }

    static void trace(Object... o) { System.out.println(Arrays.deepToString(o));}
}

class Reader {
    private final InputStream sc;
    private final byte[] buf = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;

    public Reader() { this(System.in);}
    public Reader(InputStream source) { this.sc = source;}

    private boolean hasNextByte() {
        if (ptr < buflen) return true;
        ptr = 0;
        try{
            buflen = sc

.read(buf);
        }catch (IOException e) {e.printStackTrace();}
        if (buflen <= 0) return false;
        return true;
    }

    private int readByte() { if (hasNextByte()) return buf[ptr++]; else return -1;}

    private boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}

    private void skip() { while(hasNextByte() && !isPrintableChar(buf[ptr])) ptr++;}

    public boolean hasNext() {skip(); return hasNextByte();}

    public String next() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while (isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    public long nextLong() {
        if (!hasNext()) throw new NoSuchElementException();
        boolean minus = false;
        long num = readByte();

        if(num == '-'){
            num = 0;
            minus = true;
        }else if (num < '0' || '9' < num){
            throw new NumberFormatException();
        }else{
            num -= '0';
        }
        
        while(true){
            int b = readByte();
            if('0' <= b && b <= '9')
                num = num * 10 + (b - '0');
            else if(b == -1 || !isPrintableChar(b))
                return minus ? -num : num;
            else
                throw new NoSuchElementException();
        }
    }

    public int nextInt() {
        long num = nextLong();
        if (num < Integer.MIN_VALUE || Integer.MAX_VALUE < num)
            throw new NumberFormatException();
        return (int)num;
    }

    public double nextDouble() {
        return Double.parseDouble(next());
    }

    public char nextChar() {
        if (!hasNext()) throw new NoSuchElementException();
        return (char)readByte();
    }

    public String nextLine() {
        while (hasNextByte() && (buf[ptr] == '\n' || buf[ptr] == '\r')) ptr++;
        if (!hasNextByte()) throw new NoSuchElementException();

        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while (b != '\n' && b != '\r') {
            sb.appendCodePoint(b);
            b = readByte();
        }

        return sb.toString();
    }

    public int[] nextIntArray(int n) {
        int[] res = new int[n];
        for (int i=0; i<n; i++) res[i] = nextInt();
        return res;
    }

    public char[] nextCharArray(int n) {
        char[] res = new char[n];
        for (int i=0; i<n; i++) res[i] = nextChar();
        return res;
    }

    public void close() {try{ sc.close();}catch(IOException e){ e.printStackTrace();}};
}