A. Anagrams
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

Consider the positional numeral system with a given base b. A positive integer x is called b-anagram of a positive integer y if they have the same length of representation in this system (without leading zeroes) and y can be obtained by rearranging the digits of x.

A positive integer k is called b-stable if for every integer m that is divisible by k all its b-anagrams are also divisible by k. Your task is to find all b-stable integers k for a given base b.

Input

The only line of the input contains an integer b — the base of the given positional numeral system (2 ≤ b ≤ 2·109).

Output

Print all b-stable integers k represented in the standard decimal numeral system. They must be printed in ascending order.

Examples
Input
3
Output
1 2
Input
9
Output
1 2 4 8
Input
33
Output
1 2 4 8 16 32