3214. [CH 5E26]扑克牌

【题目描述】

一副不含王的扑克牌由 52 张牌组成，由红桃、黑桃、梅花、方块 4 组牌组成，每组 13 张不同的面值。

现在给定 52 张牌中的若干张，请计算将它们排成一列，相邻的牌面值不同的方案数。

牌的表示方法为 XY，其中 X 为面值，为 2、3、4、5、6、7、8、9、T、J、Q、K、A 中的一个。

Y 为花色，为 S、H、D、C 中的一个。

如 2S、2H、TD 等。

【输入格式】

第一行为一个整数 T，表示共有 T 组测试数据。

之后每组数据占一行。

这一行首先包含一个整数 N，表示给定的牌的张数，接下来 N 个由空格分隔的字符串，每个字符串长度为 2，表示一张牌。

每组数据中的扑克牌各不相同。

【输出格式】

对于每组数据输出一行，形如 Case #X: Y，X 为数据组数，从 1 开始，Y 为可能的方案数。

由于答案可能很大，请输出对 $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

【数据规模与约定】

$1\leq T\leq 20000,1\leq N\leq 52$