Prime_Ring

Prime Ring
Một vòng gồm N phần tử hình tròn. Trong mỗi hình tròn sẽ chứa một số nguyên P và tổng hai số nguyên trong hai hình tròn cạnh nhau trên vòng tròn tạo thành một số nguyên tố. Nhiệm vụ của bạn là với một chuỗi gồm N phần tử số nguyên, đưa ta tổng số cách xếp N phần tử đó vào vòng tròn thỏa mãn yêu cầu trên.
 
Ví dụ
Ta có đầu vào là một dãy gồm 6 phần tử: 1, 2, 3, 4, 5, 6. Thì đầu ra sẽ có 2 cách xếp là cách 1: 1 - 4 - 3 - 2 - 5 - 6 và cách 2: 1 - 6 - 5 - 2 -  3 - 4

 
Cách 1: 1 - 4 - 3 - 2 - 5 - 6
 
Input
Dòng đầu liên là T chính là số testcase (T ≤ 100). Mỗi testcase sẽ bao gồm 2 dòng:
Dòng đầu tiên là N chính là số lượng phần tử các số nguyên. (3 ≤ N ≤ 16)\
Dòng thứ hai là một dãy gồm N số nguyên P ( 1 ≤ P ≤ 50)
 
Output
Kết quả được in ra trên một dòng theo định sạng sau: “Case number_testcase: answer”
 
Sample
Input
2
8
1 2 3 4 5 6 7 8
6
1 2 3 4 5 6
 
 
Output
Case 1: 4
Case 2: 2






###################################################################33
Input
100
3
1 2 3 
4
1 2 3 4 
5
1 2 3 4 5 
6
1 2 3 4 5 6 
7
1 2 3 4 5 6 7 
8
1 2 3 4 5 6 7 8 
9
1 2 3 4 5 6 7 8 9 
10
1 2 3 4 5 6 7 8 9 10 
11
1 2 3 4 5 6 7 8 9 10 11 
12
1 2 3 4 5 6 7 8 9 10 11 12 
13
1 2 3 4 5 6 7 8 9 10 11 12 13 
14
1 2 3 4 5 6 7 8 9 10 11 12 13 14 
15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 
16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 
16
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 
9
3 4 5 6 7 8 9 10 11 
6
7 8 9 10 11 12 
15
11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 
15
7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 
10
8 9 10 11 12 13 14 15 16 17 
16
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 
10
4 5 6 7 8 9 10 11 12 13 
16
5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 
14
9 10 11 12 13 14 15 16 17 18 19 20 21 22 
12
7 8 9 10 11 12 13 14 15 16 17 18 
13
6 7 8 9 10 11 12 13 14 15 16 17 18 
15
5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 
8
9 10 11 12 13 14 15 16 
9
8 9 10 11 12 13 14 15 16 
4
9 10 11 12 
4
11 12 13 14 
10
5 6 7 8 9 10 11 12 13 14 
8
12 13 14 15 16 17 18 19 
14
7 8 9 10 11 12 13 14 15 16 17 18 19 20 
6
4 5 6 7 8 9 
7
6 7 8 9 10 11 12 
8
7 8 9 10 11 12 13 14 
10
4 5 6 7 8 9 10 11 12 13 
4
11 12 13 14 
14
7 8 9 10 11 12 13 14 15 16 17 18 19 20 
3
10 11 12 
6
12 13 14 15 16 17 
4
4 5 6 7 
8
11 12 13 14 15 16 17 18 
13
8 9 10 11 12 13 14 15 16 17 18 19 20 
3
5 6 7 
11
9 10 11 12 13 14 15 16 17 18 19 
13
5 6 7 8 9 10 11 12 13 14 15 16 17 
3
11 12 13 
9
8 9 10 11 12 13 14 15 16 
3
12 13 14 
13
3 4 5 6 7 8 9 10 11 12 13 14 15 
15
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 
8
11 12 13 14 15 16 17 18 
4
6 7 8 9 
7
7 8 9 10 11 12 13 
13
3 4 5 6 7 8 9 10 11 12 13 14 15 
13
9 10 11 12 13 14 15 16 17 18 19 20 21 
4
11 12 13 14 
7
12 13 14 15 16 17 18 
3
6 7 8 
10
11 12 13 14 15 16 17 18 19 20 
7
5 6 7 8 9 10 11 
14
4 5 6 7 8 9 10 11 12 13 14 15 16 17 
6
8 9 10 11 12 13 
8
11 12 13 14 15 16 17 18 
13
3 4 5 6 7 8 9 10 11 12 13 14 15 
8
9 10 11 12 13 14 15 16 
8
9 10 11 12 13 14 15 16 
12
8 9 10 11 12 13 14 15 16 17 18 19 
5
5 6 7 8 9 
15
12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 
12
6 7 8 9 10 11 12 13 14 15 16 17 
4
5 6 7 8 
7
3 4 5 6 7 8 9 
8
9 10 11 12 13 14 15 16 
14
10 11 12 13 14 15 16 17 18 19 20 21 22 23 
12
7 8 9 10 11 12 13 14 15 16 17 18 
16
5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 
11
3 4 5 6 7 8 9 10 11 12 13 
4
7 8 9 10 
11
3 4 5 6 7 8 9 10 11 12 13 
16
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 
6
10 11 12 13 14 15 
4
10 11 12 13 
8
6 7 8 9 10 11 12 13 
10
12 13 14 15 16 17 18 19 20 21 
12
11 12 13 14 15 16 17 18 19 20 21 22 
4
11 12 13 14 
13
9 10 11 12 13 14 15 16 17 18 19 20 21 
13
3 4 5 6 7 8 9 10 11 12 13 14 15 
8
11 12 13 14 15 16 17 18 
7
4 5 6 7 8 9 10 
5
8 9 10 11 12 
11
12 13 14 15 16 17 18 19 20 21 22 
5
10 11 12 13 14 
5
6 7 8 9 10 
4
4 5 6 7 
7
3 4 5 6 7 8 9 
4
9 10 11 12