在图论中，图 $G$ 的顶点覆盖（vertex cover）是一个顶点集合 $S$，使得图中的每一条边都至少与 $S$ 中的一个顶点相关联。也就是说，对于图中的每一条边 $(u, v)$，顶点 $u$ 或 $v$ 必须在顶点覆盖 $S$ 中。

现在，Kamilah 向你展示了一个无向图 $G$，该图没有自环或重边，且每个顶点都有一个权重。她可以通过 $S$ 中所有顶点的权重之积来评估图 $G$ 的一个顶点覆盖 $S$。在此处，空集（数字集合）的乘积定义为 1。

你需要计算图 $G$ 所有顶点覆盖的上述评估值之和。

输入格式

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

对于每个测试用例，第一行包含三个整数 $n$ ($1 \le n \le 36$) 和 $m$ ($0 \le m \le \frac{n(n-1)}{2}$)，分别表示图 $G$ 的顶点数和边数，以及一个用于输出的质数 $q$ ($10^8 \le q \le 10^9$)。

第二行包含 $n$ 个整数，其中第 $i$ 个整数是图 $G$ 中第 $i$ 个顶点的权重。所有权重都在 $1$ 到 $10^9$ 的范围内。

接下来的 $m$ 行，每行包含两个整数 $u$ 和 $v$ ($1 \le u, v \le n$)，描述了第 $u$ 个顶点和第 $v$ 个顶点之间的一条边。

我们保证满足 $n > 18$ 的测试用例不超过 36 个。

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是从 1 开始的测试用例编号，$y$ 是答案对 $q$ 取模后的余数。

样例

输入 1

2
4 3 998244353
1 1 1 1
1 2
2 3
3 4
4 6 998244353
1 1 1 1
1 2
1 3
1 4
2 3
2 4
3 4

输出 1

Case #1: 8
Case #2: 5