#354 Permutation of the Year 2

Statement

Statement language

Let $N=2026$ . A permutation $(a_1,a_2,\cdots,a_N)$ of $(1,2,\cdots,N)$ is called a permutation of the year if it satisfies the following condition.

For every integer $i$ ( $1 \leq i \leq N$ ), $a_i+a_{i+1}$ is prime. Here, .

Construct a permutation of the year.

Input

The input is given in the following format.

$N$

Output

Print a permutation of the year $a_1, a_2, \cdots, a_N$ on the first line, separated by spaces.

Constraints

$N=2026$ .

Subtasks

#	Score	Constraints
1	100	No additional constraints.

Samples

Input

8

Output

1 6 7 4 3 8 5 2

This sample is for reference only and is not included in the actual judge data.