题目描述

有编号从1到n的n个球，将其放入一排n个盒子里去，要求相邻两个盒子里球的编号之和为素数，问，输入n后，输出符合条件的摆放方法的个数。

输入

输入n，1<=n<=15

输出

输出符合条件的摆放个数

样例

3

2

Hint

说明：输入n=3，只有 （1，2，3）和（3，2，1）符合要求