题目描述

输入正整数 $n$，把整数 $1,2,\dots ,n$ 组成一个环，使得相邻两个整数之和均为素数。输出时，从整数 $1$ 开始逆时针排列，同一个环只输出一次。$n\leq 16$，保证一定有解。

注意：环的第一个数一定是 $1$。

例如下图就是一个素数环。

输入格式

一行， 1 个正整数，表示素数环的大小 $n$。

输出格式

按字典序输出所有大小为 $n$ 的素数环，每行一个环，包括 $1\sim n$ 这 $n$ 个数，每个数之间用一个空格隔开。

样例

8

1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2