For an undirected connected graph of $n$ vertices, where the $i$-th vertex has a weight of $v_i$, we define the value of a simple path$^{\text{∗}}$ $l_1, l_2, \ldots, l_m$ as $v_{l_1}\oplus v_{l_2}\oplus\cdots\oplus v_{l_m}$$^{\text{†}}$. We call the graph balanced if and only if:

• For every $1\le p \lt q\le n$, all simple paths from $p$ to $q$ have the same value.

Aquawave has given you an undirected connected graph of $n$ vertices and $m$ edges, and the $i$-th vertex in the graph has a weight of $a_i$. However, some of the weights are missing, represented by $-1$.

Aquawave wants to assign an integer weight between $0$ and $V-1$ to each vertex with $a_i=-1$, so that the graph will be balanced.

You have to help Aquawave find the number of ways to assign weights to achieve the goal, modulo $998\,244\,353$.

$^{\text{∗}}$A simple path from $c$ to $d$ is a sequence of vertices $l_1, l_2, \ldots, l_m$, where $l_1=c$, $l_m=d$, such that there is an edge between $l_i$ and $l_{i+1}$ for every $1\le i\le m-1$, and there are no repeated vertices, i.e. $l_i\ne l_j$ for $1\le i \lt j\le n$. $^{\text{†}}$$\oplus$ denotes the bitwise XOR operation.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains three integers $n$, $m$, and $V$ ($2\le n\le 2\cdot 10^5$, $n-1\le m\le \min\left(\frac{n(n-1)}{2}, 4\cdot 10^5\right)$, $1\le V\le 10^9$) — the number of vertices, the number of edges, and the upper bound of weights.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-1\le a_i\le V-1$) — the weights of the vertices. $a_i=-1$ represents that the weight of the $i$-th vertex is missing.

Then $m$ lines follow, the $i$-th line containing two integers $u$ and $v$ ($1\le u,v\le n$) — the two vertices that the $i$-th edge connects.

It is guaranteed that the given graph is simple and connected.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$, and the sum of $m$ over all test cases does not exceed $4\cdot 10^5$.

Output

For each test case, output a single integer — the number of ways to assign weights to make the graph balanced, modulo $998\,244\,353$.

Note

In the first test case, there are four possible assignments:

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

It can be shown that all of these assignments can make the graph balanced.

In the second test case, we will pick $(p,q)=(1,5)$. The simple path $1\to 2\to 5$ has a value of $2\oplus 2\oplus 2=2$, and the simple path $1\to 3\to 5$ has a value of $2\oplus a_3\oplus 2=a_3$, so the only possible value for $a_3$ is $2$. It can be shown that $a_3=2$ can make the graph balanced.

In the fifth test case, the given graph is a tree, so there is only one simple path between any two vertices. Thus, we can assign an arbitrary value between $0$ and $V-1$ to each $a_i$, and the answer is $1\,000\,000\,000^3\bmod998\,244\,353=747\,068\,572$.