素数环(Prime Ring)

题目描述

将数字 1~n 组成一个数字序列（不要求有序），要求任意相邻两个数的和都是素数，并且由于序列首尾相邻形成环，第一个数与最后一个数的和也必须是素数。这样的序列称为一个素数环。给定 n，请输出所有的素数环。

为避免重复，固定环的第一个数为 1，按字典序输出所有方案。

输入格式

一行一个整数 n。

输出格式

每行一个素数环方案，为 1~n 的一个排列，数字直接连写、之间没有空格，按字典序输出。若没有合法方案（如 n 为奇数）则不输出任何内容。

样例输入

8

样例输出

12385674
12583476
14765832
16743852

数据范围

1 ≤ n ≤ 16。