Problem Description

A standard deck of playing cards without jokers consists of $52$ cards, divided into $4$ suits: hearts, spades, clubs, and diamonds. Each suit has $13$ cards with different ranks. Now you are given some cards from these $52$ cards. Please compute the number of ways to arrange them into a line such that any two adjacent cards have different ranks.

A card is represented as XY, where X is the rank, one of 2,3,4,5,6,7,8,9,T,J,Q,K,A. Y is the suit, one of S,H,D,C. For example, 2S, 2H, TD, etc.

Input Format

The first line contains an integer $T$, the number of test cases.

Each test case occupies one line. The line first contains an integer $N$, meaning the number of given cards, followed by $N$ space-separated strings. Each string has length $2$ and represents one card. All cards in the same test case are distinct.

Output Format

For each test case, output one line in the form Case #X: Y. $X$ is the test case number starting from $1$. $Y$ is the number of valid arrangements. Since the answer may be very large, output the value modulo $2^{64}$.

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

Hint

Translated by ChatGPT 5