色多项式是一种图多项式。它将图的着色数作为颜色数量的函数进行计数。

确切地说，对于无向图 $G$，$\chi_G(k)$ 计数了其顶点的 $k$-着色方案数。此处，$G$ 的顶点 $k$-着色是指为 $G$ 的每个顶点分配 $k$ 种可能颜色之一，使得没有两个相邻的顶点被分配相同的颜色。存在唯一的多项式 $\chi_G(x)$，当其在任何整数 $k \ge 0$ 处求值时，结果与 $\chi_G(k)$ 一致。如果 $G$ 有 $n$ 个顶点，则色多项式 $\chi_G(x)$ 是一个次数恰好为 $n$ 的整系数多项式。

Malak 可以利用色多项式解决几个有趣的问题，包括关于无环定向的问题。在图论中，无向图的无环定向是指为每条边分配一个方向（定向），使得该定向不形成任何有向环，从而将其转化为一个有向无环图（DAG）。每个图 $G$ 恰好有 $|\chi_G(-1)|$ 种不同的无环定向，因此从这个意义上讲，无环定向可以被解释为一种用 $-1$ 种颜色进行的着色。

现在 Malak 向你展示了一个完全二分图，其两个顶点集的大小分别为 $n$ 和 $m$，记作 $K_{n,m}$。你需要计算 $K_{n,m}$ 的不同无环定向的数量。

输入格式

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

每个测试用例由三个整数 $n, m$（$1 \le n, m \le 60000$）描述，它们是给定完全二分图的顶点集大小；$q$（$10^8 \le q \le 10^9$）是一个用于输出的质数。

我们保证不超过 $60$ 个测试用例满足 $n > 60$ 或 $m > 60$，且不超过 $6$ 个测试用例满足 $n > 600$ 或 $m > 600$。

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是从 $1$ 开始的测试用例编号，$y$ 是不同无环定向数量除以 $q$ 的余数。

样例

输入 1

4
1 1 998244353
1 2 998244353
2 1 998244353
2 2 998244353

输出 1

Case #1: 2
Case #2: 4
Case #3: 4
Case #4: 14