As the Christmas is coming, Little Santa is preparing the Christmas presents. Little Santa has N presents. All the presents are numbered from 1 to N. He noticed that different permutations of presents will have different beauty. Beauty of a permutation of N presents is the number of squares among the prefix sums. Little Santa wants to maximize the beauty.

Note: Prefix sums of a $(1, 2, 3)$ are $(1, 1 + 2, 1 + 2 + 3) = (1, 3, 6)$. You can read about it here.

You do not have to find an optimal solution, so your score will depend on the beauty of the permutation that you output. A higher beauty will lead to a higher score.

Input format:

First line of input contains a single integer N $(1 \le N \le 10000)$ - length of permutation.

Tests:

During the contest problem will contain 100 tests. The i-th test contains random number from segment $[100 \cdot (i - 1) + 1, 100 * i]$.

After contest we will add 100 additional tests. We will use same generator but with differtent seed.

Scoring:

You score for each test is $\frac{a}{n} \cdot 10^6$, where a is number of squares among the prefix sums in permutation printed by your solution.