题目描述

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

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

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

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

如 2$S$、2$H$、$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≤T≤20000, 1≤N≤52$

来源

• 算法竞赛进阶指南