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.