Given an integer n. Initially you have permutation p of size n: \(p_i = i\). To build new array a from p following steps are done while permutation p is not empty:

1. Choose maximum existing element in p and define it as x;
2. Choose all such y in p that \(\gcd(x, y) \neq 1\);
3. Add all chosen numbers into array a in decreasing order and remove them from permutation.

Your task is to find a after p became empty.

Note: \(\gcd(a, b)\) is the greatest common divisor of integers a and b.

Input format

Input contains single integer n (\(1 \leq n \leq 2 \cdot 10^6\)) — the size of permutation p.

Output format

Print n integers — array a.