题目描述

如图所示为一个由 $n$ 个圆圈构成的圆环。将自然数 $1，2，...，n$ 放入圆圈内，并且要求任意两个相邻的圆圈内的数字之和为素数。请问给你圆圈数，你能给出放置自然数的所有正确方案吗？

注意：圆圈中的数字一定是从 $1$ 开始的，并且连续不重复。

输入输出格式

输入

输入 $n(1<=n<=17)$ 。

输出

把 $1$ 放在第一位置，按照字典顺序不重复的输出所有解(顺时针，逆时针算不同的两种)，相邻两数之间严格用一个整数隔开，每一行的末尾不能有多余的空格。

如果没有答案请输出"no answer"。

样例

输入1

8

输出1

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

时间及空间限制

1s, 256MB.