human
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...
Solve the task in PYTHON.
assistant
#Here is the Python program you requested.

#! /usr/bin/env python
# -*- coding: utf-8 -*-

import os
import sys
import itertools
import math
from collections import Counter, defaultdict

class Main(object):
    
    def __init__(self):
        pass

    def solve(self):
        '''
        insert your code
        '''
        p = self.sieve(300001)
        while True:
            n = input()
            if n == 1:
                break
            ans = '{0}: '.format(n)
            seq = []

            for i in range(len(p)):
                if n % p[i] == 0:
                    seq.append(str(p[i]))

            ans += ' '.join(seq)
            print ans
                    
        return None
    
    def mark(self, s, x):
        for i in xrange(x + x, len(s), x):
            s[i] = False

    def sieve(self, n):
        s = [True] * n
        for x in xrange(n):
            if x % 7 != 1 and x % 7 != 6:
                s[x] = False
        for x in xrange(2, int(n ** 0.5) + 1):
            if s[x]:
                self.mark(s, x)
        return [i for i in xrange(n) if s[i] and i > 1]

if __name__ == '__main__':
    m = Main()
    m.solve()