Code Jam 团队的第一种加密货币 jamcoins 从未流行起来。今年，我们再次尝试推出 hexacoins，其名称源于它们对 16 进制的使用。要“挖掘”一个 $D$ 位的 hexacoin，需要处理使用恰好 $D$ 个 16 进制位（包括必要的前导零）的整数。每个值代表一个 $0$ 到 $16^D - 1$（含）之间的整数。16 进制位通常用数字 $0$ 到 $9$ 和大写字母 $A$ 到 $F$ 表示。例如，当 $D=3$ 时，F2B、0C8 和 000 是有效值，分别对应 10 进制值 3883、200 和 0。另一方面，当 $D=3$ 时，1234、DF、C0DE 和 JAM 不是有效值。
在对 $D$ 位 16 进制值进行加法运算时，任何溢出的位都会被丢弃。也就是说，加法是在模 $16^D$ 下进行的。例如，F2B + 0C8 = FF3（10 进制为 4083），而 F2B + F2B = E56（10 进制为 3670，因为求和结果为 7766，取模 $16^3$ 后得到 3670）。
要“挖掘”一个 $D$ 位的 hexacoin，计算机必须执行以下步骤：
- 选择一个包含 $N$ 个 $D$ 位 16 进制值的列表 $L = [L_1, L_2, \dots, L_N]$。
- 选择一个 $D$ 位 16 进制值的目标范围：从 $S$ 到 $E$（含）之间的数字。
- 从所有 $16!$ 种排列中均匀随机选择一个 16 进制位（$0$ 到 $F$）的排列 $P$。
- 将 $P$ 应用于列表中所有数字的所有位，创建一个包含 $N$ 个 $D$ 位 16 进制值的新列表 $L'$。形式上，$L'$ 中第 $i$ 个元素的第 $j$ 位是将 $P$ 应用于 $L$ 中第 $i$ 个元素的第 $j$ 位的结果。
- 从 $L'$ 中不放回地均匀随机选择一对元素，该选择独立于排列的选择。
- 计算所选两个元素的和（丢弃溢出位）。
如果最后一步计算出的和在 $S$ 到 $E$（含）之间，则表示找到了一个 hexacoin！例如，假设： $L = [134, 000, FFB, 000, AA9]$。 $S = 85C$ 且 $E = EDF$。 * 计算机恰好选择了 $P = (0 \to 4, 1 \to A, 2 \to 2, 3 \to 8, 4 \to 9, 5 \to B, 6 \to C, 7 \to 7, 8 \to F, 9 \to 1, A \to 0, B \to 3, C \to 5, D \to 6, E \to E, F \to D)$。
那么，当 $P$ 应用于 $L$ 时，得到的 $L'$ 为 $[A89, 444, DD3, 444, 001]$。注意 $P$ 不应用于 $S$ 和 $E$。
共有 $(5 \times 4) / 2 = 10$ 对值可供选择，每一对被选中的概率为 $1/10$。落在范围内的和只有 A89 + DD3 = 85C, 444 + 444 = 888, A89 + 001 = A8A, DD3 + 001 = DD4, 以及 A89 + 444 = ECD（两次）。
前两个步骤已经完成，你知道所选的列表 $L$ 和范围 $[S, E]$。在执行剩余过程后，找到 hexacoin 的概率是多少？
输入格式
输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例包含三行。第一行包含两个整数 $N$ 和 $D$：给定列表的大小和要处理的位数。第二行包含两个 $D$ 位 16 进制数 $S$ 和 $E$：目标范围的包含性下界和上界。接下来还有一行，包含 $N$ 个 $D$ 位 16 进制数 $L_1, L_2, \dots, L_N$，表示列表中的值。
输出格式
对于每个测试用例，输出一行 Case #x: y z，其中 $x$ 是测试用例编号（从 1 开始），$y$ 和 $z$ 是非负整数，使得分数 $y/z$ 表示在上述条件下找到 hexacoin 的概率。$x, y, z$ 均必须以 10 进制表示。如果 $y$ 和 $z$ 有多个可接受的值，请选择使得 $z$ 最小的一组。
数据范围
时间限制：每个测试集 90 秒。 内存限制：1GB。 $2 \le N \le 450$。 $S$ 恰好包含 $D$ 个字符。 $S$ 的每个字符都是一个 16 进制位。 $E$ 恰好包含 $D$ 个字符。 $E$ 的每个字符都是一个 16 进制位。 $S \le E$。 对于所有 $i$，$L_i$ 恰好包含 $D$ 个字符。 对于所有 $i$，$L_i$ 的每个字符都是一个 16 进制位。
子任务
测试集 1（可见判定） $1 \le T \le 100$ $2 \le D \le 3$
测试集 2（隐藏判定） $1 \le T \le 100$ $2 \le D \le 4$
测试集 3（隐藏判定） $1 \le T \le 10$ $2 \le D \le 5$
样例
样例输入 1
4 2 2 10 10 00 FF 2 2 10 11 00 FF 4 3 FFF FFF 230 A10 010 F70 4 3 AFF FFF 230 A10 010 F70
样例输出 1
Case #1: 7 120 Case #2: 1 15 Case #3: 0 1 Case #4: 2731 8736
说明
在样例 1 中，目标范围仅为一个值 10。由于结果以 0 结尾，分配给最后两位 0 和 F 的值的和也必须以 0 结尾。由于 $P[0]$ 和 $P[F]$ 是不同的值，它们的和不可能是 0。因此，$P[0] + P[F]$ 必须是 10（16 进制）。有 7 对不同的数字可以实现这一点。$P[0]$ 和 $P[F]$ 不能同时为 8。所有 7 对数字都会导致总和为 10（在丢弃溢出的 1 之后）。因此，有 14 种将不同数字分配给 0 和 F 的方式可以得到 hexacoin。对于这些数字，有 $16 \times 15$ 种可能的分配方式，因此结果为 $14/240 = 7/120$。
在样例 2 中，我们需要将结果恰好为 11 的概率加到样例 1 的结果中。唯一能实现这一点的情况是 0 和 F 被分配为 0 和 1（顺序不限）。这种情况的概率为 $2/240 = 1/120$，从而得到总概率 $7/120 + 1/120 = 8/120 = 1/15$。
在样例 3 中，请注意无论计算机从列表中选择哪种排列和哪对数字，我们相加的两个数字的末位都相同。这会产生一个偶数结果，即使在模 $16^3$ 之后也是如此。由于范围内的唯一值是奇数，我们在这个案例中没有希望挖掘到 hexacoin。注意 0 2 是无效的答案表示，因为 $z$ 不是最小的。