题目描述

输入n，输出1-n的所有全排列，使相邻的两个数字的和是质数。

输入格式

一行只有一个数n。

输出格式

满足条件的排列，按字典序输出。

样例

输入数据 1

5

输出数据 1

1 4 3 2 5

3 4 1 2 5

5 2 1 4 3

5 2 3 4 1

提示

1≤n≤9