不含环或多重边的图称为简单图。

顶点着色是指为图的每个顶点分配颜色的过程。合法的顶点着色是指在着色后，没有任何边连接两个颜色相同的顶点。

对于一个无向简单图，如果其每个顶点的所有邻接顶点中，每种颜色都恰好出现一次，则称该着色为 $n$-彩虹着色。注意，$n$-彩虹着色不是合法的着色，因为相邻顶点可能具有相同的颜色。

如果一个无向简单图至少存在一种合法的 $n$-彩虹着色，则称该图为 $n$-彩虹图。两个 $n$-彩虹图 $G$ 和 $H$ 被称为同构的，如果存在双射 $f : V(G) \to V(H)$，使得 $G$ 中的两个顶点相邻当且仅当它们在 $H$ 中的像相邻。

你的任务是计算具有 $2n$ 个顶点的不同构的 $n$-彩虹图的数量，并将该数量对一个素数 $p$ 取模。

输入格式

输入包含多个测试用例。第一行包含一个正整数 $T$，表示测试用例的数量，最多为 $1000$。

对于每个测试用例，唯一的一行包含两个整数 $n$ 和 $p$，其中 $1 \le n \le 64$，$n + 1 \le p \le 2^{30}$ 且 $p$ 是一个素数。

我们保证满足 $n \ge 16$、$n \ge 32$ 和 $n \ge 48$ 的测试用例数量分别不超过 $200$、$100$ 和 $20$。

输出格式

对于每个测试用例，输出一行包含 “Case #x: y”（不含引号），其中 $x$ 是从 $1$ 开始的测试用例编号，$y$ 是答案对 $p$ 取模的结果。

样例

输入 1

5
1 11059
2 729557
3 1461283
4 5299739
63 49121057

输出 1

Case #1: 1
Case #2: 1
Case #3: 2
Case #4: 3
Case #5: 5694570

说明

如果你想出的解法时间复杂度渐进于 $p(n)$（$n$ 的划分数）或类似复杂度，你可能需要知道 $p(16) = 231$，$p(32) = 8349$，$p(48) = 147273$ 以及 $p(64) = 1741630$。

下图展示了前四个样例中提到的所有非同构彩虹图。

图 1：具有 2 个顶点的非同构 1-彩虹图

图 2：具有 4 个顶点的非同构 2-彩虹图

图 3：具有 6 个顶点的非同构 3-彩虹图

图 4：具有 8 个顶点的非同构 4-彩虹图