题目背景

经典的回溯算法应用问题，探索数字排列成环的素数约束条件。

题目描述

将从 $1$ 到 $n$（$2 \le n \le 10$）这 $n$ 个整数摆成一个环，要求相邻的两个数的和必须是素数。请按照字典序由小到大输出所有可能的摆放形式。

输入格式

一个整数 $n$（$2 \le n \le 10$）。

输出格式

前若干行，每行输出一个素数环的解，格式为 序号: 数字序列（数字之间用空格分隔）； 最后一行，输出 total: 解的总数。

输入输出样例

输入 #1

4

输出 #1

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

输入 #2

6

输出 #2

1:1 4 3 2 5 6
2:1 6 5 2 3 4
3:2 3 4 1 6 5
4:2 5 6 1 4 3
5:3 2 5 6 1 4
6:3 4 1 6 5 2
7:4 1 6 5 2 3
8:4 3 2 5 6 1
9:5 2 3 4 1 6
10:5 6 1 4 3 2
11:6 1 4 3 2 5
12:6 5 2 3 4 1
total:12

说明/提示

• 对于 $100\%$ 的数据，$2 \le n \le 10$；
• 输出需严格按照字典序排列。