Description

输入正整数 n，把整数 1,2,…,n 组成一个环，使得相邻两个整数之和均为素数。请输出所有可能的摆放形式。

输入

一个整数 n(2≤n≤10）

输出

按从小到大的顺序输出所有的素数环的解，最后一行，输出解的总数。

Samples

4

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

Limitation

1s, 1024KiB for each test case.