Rikka 知道冒泡排序是一种简单但优美的算法，快速排序是一种复杂但高效的算法，而希尔排序则是一种怪异但实用的算法。Rikka 对所有的排序算法都很感兴趣，她可以为 ICPC 竞赛布置任意多道新题。

Rikka 讨厌那些反复使用相同想法出题的人，她希望自己不要成为她所讨厌的那种人。尽管她已经布置了几道关于排序算法（如归并排序和插入排序）的题目，但她决定向你展示最后一道关于排序算法的题目，以永远结束这个系列。

在这里，Rikka 引入了排序网络，并首先定义了一个比较器。对于一个由 $n$ 个最小正整数组成的排列 $A = a_1, a_2, \dots, a_n$，一个比较器 $[u, v]$ ($u \neq v$) 将 $A$ 中的第 $u$ 个元素和第 $v$ 个元素按非递减顺序排列。形式上，比较器是一个满足以下条件的映射 $[u, v]$：

• $[u, v](a_u) = \min(a_u, a_v)$；以及
• $[u, v](a_v) = \max(a_u, a_v)$；以及
• $[u, v](a_k) = a_k$，对于所有 $k \neq u$ 且 $k \neq v$。

Rikka 将排序网络定义为比较器的组合，并为你提供了一个包含 $k$ 个有序比较器的排序网络。现在，Rikka 希望你计算有多少个 $1$ 到 $n$ 的排列，在经过给定的排序网络后，会变成一个“几乎有序”的排列。她说，如果一个 $1$ 到 $n$ 的排列的最长上升子序列长度至少为 $(n - 1)$，那么它就是几乎有序的。

输入格式

输入包含多个测试用例，第一行包含一个整数 $T$ ($1 \le T \le 100$)，表示测试用例的数量。

对于每个测试用例，第一行包含三个整数 $n$ ($2 \le n \le 50$)，表示排列的长度；$k$ ($0 \le k \le 10$)，表示比较器的数量；以及 $q$ ($10^8 \le q \le 10^9$)，表示用于输出的质数。

接下来 $k$ 行，第 $i$ 行包含两个整数 $u$ 和 $v$ ($1 \le u < v \le n$)，表示第 $i$ 个比较器 $[u, v]$。

输出格式

对于每个测试用例，输出一行，包含一个整数，即满足要求的排列数量对 $q$ 取模的结果。

样例

样例输入 1

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

样例输出 1

10
14
24
24