187-consecutive-primes

Consecutive Primes

Challenge Description:

Alice has an even number of N beads, and each bead has a number from 1 to N painted on it. She would like to make a necklace out of all the beads, with a special requirement: any two beads next to each other on the necklace must sum to a prime number. Alice needs your help to calculate how many ways it is possible to do so.

For example:

N = 4

There are two possible ways to build the necklace. Note that the last bead connects to the first bead.

1 2 3 4
1 4 3 2

Note: The necklace should be unique.
For example: 1 2 3 4 is the same as 2 3 4 1 and 3 4 1 2 and 4 1 2 3.

So the answer is 2.

Input sample:

The inputs consists of one even integer on a line. Each integer N is 2 <= N <= 18.

For example:

2
4
5

Output sample:

Print a line containing the number of ways to make a necklace according to the above rules. If not even number print 0.

For example:

1
2
0

Constraints:

1. 2 <= N <= 18
2. Number of test cases is 5.