There is an $n \times m \times l$ cube, where each cell contains a number. A cell is called "maximal" if the number in it is greater than the numbers in all other cells that share at least one coordinate with it.

Now, the $n \times m \times l$ numbers from $1$ to $n \times m \times l$ are randomly filled into the $n \times m \times l$ cells with equal probability (i.e., every number appears exactly once in a random position). Find the probability that there are exactly $k$ maximal numbers. The answer should be taken modulo $998244353$ (a prime number).

Input

The input contains multiple test cases. The first line contains a positive integer $T$, representing the number of test cases.

Each of the next $T$ lines contains four positive integers $n, m, l, k$, representing a query.

Output

For each query, output a single integer representing the answer modulo $998244353$.

It can be proven that the answer is always a rational number. Let it be $a/b$ (where $a$ and $b$ are coprime positive integers, and it is guaranteed that $b$ is not a multiple of $998244353$). You need to output an integer $x$ such that $0 \le x < 998244353$ and $a \equiv bx \pmod{998244353}$. It can be proven that such an $x$ exists and is unique.

Examples

Input 1

5
1 1 1 1
2 2 2 1
7 8 9 3
123 456 789 1
1000 1000 1000 10

Output 1

1
142606337
736950806
246172965
189652652

Examples

Input 2

See cube/cube2.in and cube/cube2.ans in the contestant's directory.

Constraints

• For $10\%$ of the data, $n, m \le 2$, $l \le 3$, $k = 1$.
• For $30\%$ of the data, $n, m, l, k \le 12$.
• For $40\%$ of the data, $n, m, l \le 100$.
• For $50\%$ of the data, $n, m, l \le 1000$.
• For $60\%$ of the data, $n, m, l \le 100000$, where $30\%$ of the total data guarantees $k = 1$.
• For $80\%$ of the data, $n, m, l \le 1000000$, where $40\%$ of the total data guarantees $k = 1$.
• For $100\%$ of the data, $1 \le n, m, l \le 5000000$, $1 \le k \le 100$, $1 \le T \le 10$, where $50\%$ of the data guarantees $k = 1$.