In a nutshell:

Given a bivariate polynomial $F(x, y)$ of degree $p \times q$, compute

$$\sum_{x = 0}^n \sum_{y = 0}^{\min(x, m)} \binom{x + y}{x} \binom{n - x + m - y}{n - x} F(x, y)$$

modulo $998244353$.

Each test case contains $T$ queries, and it is guaranteed that the value $m - n$ is a constant $c$ across all queries.

Input

The first line contains five integers $T, c, p, q, N$, representing the number of queries, the constant $m - n = c$, the degree of the bivariate polynomial, and the upper bound of $n$ for all queries in this test case, respectively (i.e., $n \leq N$ for all queries).

The next $T$ lines contain the test data, where each test case is provided as follows:

The first line contains two integers $n$ and $m$, guaranteed to satisfy $m - n = c$.

The next $p + 1$ lines each contain $q + 1$ integers, where the $j$-th number in the $i$-th line represents the coefficient of $x^{i - 1} y^{j - 1}$ in $F(x, y)$.

Output

Output $T$ lines, each containing an integer representing the answer to the problem.

Examples

Input 1

2 0 1 1 5
1 1 
1 1
1 1
2 2
1 2
3 4

Output 1

12
278

Constraints

For convenience, let $L = \max(N, N + c)$ be the range of coordinates in the queries.

For all test data: $1 \leq T \leq 10^5, -10^5 \leq c \leq 10^5, 1 \leq L \leq 10^5, 0 \leq (p + 1) \times (q + 1) \leq 10$. It is guaranteed that the coefficients of the input polynomial are in the range $[0, 998244353)$.

• Subtask 1 ($1$ pts): $T = 1, L \leq 10^3$
• Subtask 2 ($9$ pts): $L \leq 10^3$
• Subtask 3 ($20$ pts): $T = 1, p = q = 0$
• Subtask 4 ($20$ pts): $p = q = 0$
• Subtask 5 ($20$ pts): $T = 1$
• Subtask 6 ($10$ pts): $c = 0$
• Subtask 7 ($20$ pts): No special constraints.