Server Time: Fri Oct 30, 2020 4:49 am
Welcome ( logout
L - Playing Cards
PDF (English) Ranklist
Time Limit: 1 second(s) Memory Limit: 32 MB

In a regular card set there are 52 cards, each card has two parts, the value and the suit. The values are one of 2, 3, 4, 5, 6, 7, 8, 9, T, J, Q, K, A and the suit is one of H, S, D, C. Cards are represented first by their value and then by their suit. For example, 7H, 2C, JD etc are some cards.

Now from the regular card set, you removed some of the cards (probably 0). Your task is to find the number of ways you can place the cards in a line such that no two adjacent cards have the same value. You have to use all the cards (of course the remaining cards).

For example, 2H, 3C, 5C is a valid solution, but 5H, 5C, 7S is not.

Input

Input starts with an integer T (≤ 20000), denoting the number of test cases.

Each case starts with a line containing an integer n (1 ≤ n ≤ 52) denoting the number of remaining cards, followed by n remaining cards (a single space precedes every card). Assume that the cards are from the regular set and no card is reported more than once. Also assume that the cards will be represented as stated above.

Output

For each case, print the case number and the number of ways to place the cards in a line such that no two adjacent cards have the same value. Print the result modulo 264.

Sample Input

Output for Sample Input

5

1 TC

2 TC TS

5 2C AD AC JC JH

4 AC KC QC JC

6 AC AD AS JC JD KD

Case 1: 1

Case 2: 0

Case 3: 48

Case 4: 24

Case 5: 120

 


Problem Setter: Jane Alam Jan
Developed and Maintained by
JANE ALAM JAN
Copyright © 2012
LightOJ, Jane Alam Jan