You are given a directed graph consisting of $$$n$$$ vertices and $$$m$$$ edges. Each vertex $$$v$$$ corresponds to a positive number $$$a_v$$$. Count the number of distinct simple paths$$$^{\text{∗}}$$$ consisting of at least two vertices, such that the sequence of numbers written at the vertices along the path forms a generalized Fibonacci sequence.

In this problem, we will consider that the sequence of numbers $$$x_0, x_1, \ldots, x_k$$$ forms a generalized Fibonacci sequence if:

$$$x_0, x_1$$$ are arbitrary natural numbers.
$$$x_i = x_{i - 2} + x_{i - 1}$$$ for all $$$2 \le i \le k$$$.

Note that a generalized Fibonacci sequence consists of at least two numbers.

Since the answer may be large, output it modulo $$$998\,244\,353$$$.

$$$^{\text{∗}}$$$A simple path in a directed graph is a sequence of vertices $$$v_1, v_2, \ldots, v_k$$$ such that each vertex in the graph appears in the path at most once and there is a directed edge from $$$v_i$$$ to $$$v_{i+1}$$$ for all $$$i \lt k$$$.

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 two numbers $$$n$$$, $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le 2 \cdot 10^5$$$) — the number of vertices and the number of edges in the graph, respectively.

The second line of each test case contains $$$n$$$ natural numbers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^{18}$$$) — the numbers written at the vertices.

The next $$$m$$$ lines contain the edges of the graph; each edge is defined by two natural numbers $$$v, u$$$ ($$$1 \le v, u \le n$$$, $$$u \neq v$$$), denoting a directed edge from $$$v$$$ to $$$u$$$. It is guaranteed that there are no multiple edges in the graph.

It is guaranteed that the sum of $$$n$$$ and the sum of $$$m$$$ across all test cases do not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output the number of paths that form a generalized Fibonacci sequence, modulo $$$998\,244\,353$$$.

Note

Explanation of the first test case example (the vertex number is outside the brackets, the number written in the vertex is inside):

$\text{[math]}$ In this case, there are 5 generalized Fibonacci paths: ($$$1, 2$$$), ($$$1, 3$$$), ($$$2, 4$$$), ($$$3, 4$$$), ($$$1,3,4$$$). For example, for the path ($$$1,3,4$$$), the sequence of numbers written at the vertices along this path is: [$$$3,3,6$$$]. As can be easily seen, the third number in the sequence is the sum of the two previous ones.

Explanation of the second test case example:

$\text{[math]}$ In this case, there are 9 generalized Fibonacci paths: ($$$1, 2$$$), ($$$1, 4$$$), ($$$2, 3$$$), ($$$2, 4$$$), ($$$3, 1$$$), ($$$3, 4$$$), ($$$1, 2, 4$$$), ($$$2, 3, 4$$$), ($$$3, 1, 4$$$). Note that for the path ($$$1, 2, 3$$$), the sequence of numbers written at the vertices along this path is: [$$$1,1,1$$$], and it is not a generalized Fibonacci sequence.

Fibonacci Paths

Examples