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.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
    static void printAns(int num, ArrayList<Integer> ans) {
        Collections.sort(ans);
        String[] ansArray = new String[ans.size()];

        for (int i = 0; i < ansArray.length; i++)
            ansArray[i] = ans.get(i).toString();

        String joined = String.join(" ", ansArray);
        System.out.println(num + ": " + joined);
    }


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num;
        // ?´???°??¨?????????
        List<Integer> primeList = new ArrayList<>();

        boolean[] primeArray = new boolean[300001];
//        System.out.println(primeArray[299998]);
        for (int i = 1; i < 300000; i++) {
            if (i % 7 == 1 || i % 7 == 6)
                primeArray[i] = true; // ?????????????´???°
        }
//        System.out.println(primeArray[299998]);
        for (int i = 1; i < Math.sqrt(300000 + 1)/7 + 1; i++) {
            for (int j = i+1; j < 300000/7 + 1; j++) {
                if ((7*j-1) % (7*i+1) == 0)
                    primeArray[7*j-1] = false;
                if ((7*j+1) % (7*i+1) == 0)
                    primeArray[7*j+1] = false;
                if ((7*j-1) % (7*i-1) == 0)
                    primeArray[7*j-1] = false;
                if ((7*j+1) % (7*i-1) == 0)
                    primeArray[7*j+1] = false;
            }
        }
        for (int i = 1; i < 300000/7 + 1; i++) {
            if (primeArray[7*i-1])
                primeList.add(7*i-1);
            if (primeArray[7*i+1])
                primeList.add(7*i+1);
        }
//        System.out.println(primeList.contains(299998));
        // done

        while (true) {
            num = sc.nextInt();
            ArrayList<Integer> ans = new ArrayList<>();
            if (num == 1) break;


            for (int prime: primeList) {
                if (num % prime == 0)
                    ans.add(prime);
            }

            printAns(num, ans);
        }

    }

}