P10968 Playing Cards

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.

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.

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}$.

Translated by ChatGPT 5