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