对于一个由 $n$ 个顶点组成的无向连通图，其中第 $i$ 个顶点的权重为 $v_i$，我们定义一条简单路径 $l_1, l_2, \dots, l_m$ 的值为：

$$v_{l_1} \oplus v_{l_2} \oplus \dots \oplus v_{l_m} $$

（其中 $\oplus$ 表示按位异或运算）。

我们称该图是平衡的，当且仅当：

• 对于任意 $1 \leq p < q \leq n$，从 $p$ 到 $q$ 的所有简单路径的值都相等。

Aquawave 给了你一个由 $n$ 个顶点和 $m$ 条边组成的无向连通图，图中第 $i$ 个顶点的权重为 $a_i$。然而，其中一些权重缺失了，用 $-1$ 表示。

Aquawave 希望为每个 $a_i = -1$ 的顶点赋一个介于 $0$ 到 $V-1$ 之间的整数权重，使得该图变为平衡的。

你需要帮助 Aquawave 计算出有多少种赋值方式可以达到目标，结果对 $998244353$ 取模。

---

输入格式

每个测试点包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。

接下来是每个测试用例的描述：

• 第一行包含三个整数 $n, m, V$（$2 \leq n \leq 2 \times 10^5$，$n-1 \leq m \leq \min\left(\frac{n(n-1)}{2}, 4 \times 10^5\right)$，$1 \leq V \leq 10^9$），分别表示顶点数、边数和权重的上界。
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$-1 \leq a_i \leq V-1$），表示顶点的权重。其中 $a_i = -1$ 表示该顶点的权重缺失。
• 接下来 $m$ 行，每行包含两个整数 $u, v$（$1 \leq u, v \leq n$），表示一条连接顶点 $u$ 和 $v$ 的边。

输入保证给出的图是简单且连通的。

输入保证所有测试用例的 $n$ 之和不超过 $2 \times 10^5$，所有测试用例的 $m$ 之和不超过 $4 \times 10^5$。

---

输出格式

对于每个测试用例，输出一个整数，表示使得图平衡的赋值方式数量，对 $998244353$ 取模。

---

示例

输入

5
4 4 4
-1 -1 -1 -1
1 2
2 3
1 3
4 3
5 6 7
2 2 -1 2 2
1 2
1 3
1 4
2 5
3 5
4 5
7 8 9
-1 -1 -1 -1 0 -1 0
1 2
2 3
3 4
1 4
1 5
5 6
7 6
7 5
5 8 1000000000
1 2 3 4 -1
1 2
3 2
3 5
5 1
2 4
4 3
2 5
1 4
5 4 1000000000
-1 2 -1 3 -1
1 2
1 3
2 4
2 5

输出

4
1
9
0
747068572

---

样例说明

第一个测试用例：共有 $4$ 种可能的赋值方式：

• $a = [0,0,0,0]$
• $a = [0,0,0,1]$
• $a = [0,0,0,2]$
• $a = [0,0,0,3]$

可以证明这些赋值都能使图平衡。

第二个测试用例：取 $(p, q) = (1, 5)$，简单路径 $1 \to 2 \to 5$ 的值为 $2 \oplus 2 \oplus 2 = 2$，简单路径 $1 \to 3 \to 5$ 的值为 $2 \oplus a_3 \oplus 2 = a_3$，因此 $a_3$ 只能为 $2$。可以证明 $a_3 = 2$ 能使图平衡。

第五个测试用例：给出的图是一棵树，因此任意两点之间只有一条简单路径。我们可以为每个 $a_i$ 任意赋 $0$ 到 $V-1$ 之间的值，答案为 $1000000000^3 \bmod 998244353 = 747068572$。