悠闲的水豚们正在庆祝“水豚舒适嘉年华”。水豚主席正在切割一块凸多边形蛋糕。蛋糕有 $n$ 个色彩斑斓的角。有 $k$ 种颜色可供选择。通过进行 $m$ 条连续且互不相交的角到角的切割，主席将蛋糕切成了若干块，以招待 $m+1$ 位伙伴。有趣的是，相邻蛋糕块的角颜色必须互不相同。

请考虑切割条件，计算蛋糕角的颜色组合数。

换句话说，你得到一个形状为正 $n$ 边形的蛋糕和 $m$ 条互不相交的对角线切割，这些切割将蛋糕分成了 $m+1$ 个切片。

计算用 $k$ 种颜色为原始蛋糕的每个角着色的方案数，使得结果切片中没有两个相邻的角颜色相同。如果两个角在原始蛋糕中是连续的，或者它们是同一条切割线的端点，则认为这两个角是相邻的。

不要求必须使用所有颜色。由于方案数可能很大，请输出其对 $998\,244\,353$ 取模的结果。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 10^4$)。

接下来是各测试用例的描述。

每个测试用例的第一行包含三个整数 $n, m$ 和 $k$，分别表示蛋糕角的数量、切割的数量以及可用颜色的数量 ($3 \le n \le 10^9; 0 \le m \le 2 \cdot 10^5; 2 \le k \le 10^6$)。

接下来的 $m$ 行中，第 $i$ 行包含两个整数 $u_i$ 和 $v_i$，表示第 $i$ 条切割线连接的两个角 ($1 \le u_i < v_i \le n$)。任意两条切割线在端点之外不会重合或相交。所有切割线均为直线，且严格位于蛋糕内部。

保证所有测试用例的 $m$ 之和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出满足没有两个相邻角颜色相同的着色方案数，对 $998\,244\,353$ 取模。记住，你不必使用所有颜色。

样例

样例输入 1

4
4 1 3
1 3
5 0 2
9 4 3
1 3
1 6
4 6
6 8
3 0 1001

样例输出 1

6
0
54
1754647

说明

在第一个测试用例中，角 1 有 3 种颜色可选。角 2 有剩余的 2 种颜色可选。角 3 有剩余的 1 种颜色可选，角 4 的颜色必须与角 2 相同。因此，总共有 6 种方案。

在第二个测试用例中，我们有奇数个角和两种颜色，且每一对相邻的角都必须颜色不同；这是不可能的。