题目描述

输入正整数n，把整数1∼n组成一个环，使得相邻两个数之和均为质数。 输出所有可行的排列方案，输出时从整数1开始逆时针排列，按字典序从小到大输出。

输入格式

一个正整数n

输出格式

每行输出一个可行的排列。

输出时从整数1开始逆时针排列，按字典序从小到大输出。

输入样例 #1

6

输出样例 #1

1 4 3 2 5 6
1 6 5 2 3 4

输入样例 #2

1

输出样例 #2

1

输入样例 #3

3

输出样例 #3

数据范围与约定

1≤n≤16。