题目描述

一副不含王的扑克牌由 $52$ 张牌组成，由红桃、黑桃、梅花、方块 $4$ 组牌组成，每组 $13$ 张不同的面值。现在给定 $52$ 张牌中的若干张，请计算将它们排成一列，相邻的牌面值不同的方案数。

牌的表示方法为 $\texttt{XY}$，其中 $\texttt{X}$ 为面值，为 $\texttt{2},\texttt{3},\texttt{4},\texttt{5},\texttt{6},\texttt{7},\texttt{8},\texttt{9},\texttt{T},\texttt{J},\texttt{Q},\texttt{K},\texttt{A}$ 中的一个。$\texttt{Y}$ 为花色，为 $\texttt{S},\texttt{H},\texttt{D},\texttt{C}$ 中的一个。如 $\texttt{2S},\texttt{2H},\texttt{TD}$ 等。

输入格式

第一行为一个整数 $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