Kujou Karen is playing a fun strategy game: Slay the Spire. Initially, Karen's deck contains $2n$ cards, each with a number $w_i$ written on it. There are two types of cards, with $n$ cards of each type:

1. Attack cards: Playing one deals damage equal to the number on the card to the opponent.
2. Power cards: Playing one with a number $x$ multiplies the values of all other remaining attack cards by $x$. It is guaranteed that the numbers on all power cards are greater than 1.

Karen draws $m$ cards from the deck uniformly at random. Due to cost constraints, Karen can play at most $k$ cards. Assuming Karen always adopts the strategy that maximizes the total damage dealt, calculate the expected damage she can deal.

Let the answer be $\text{ans}$. You only need to output:

$$\left (\text{ans}\times \frac{(2n)!}{m!(2n-m)!}\right) \bmod 998244353$$

where $x!$ denotes $\prod_{i=1}^{x}i$, and specifically, $0!=1$.

Input

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

For each test case:

The first line contains three positive integers $n, m, k$.

The second line contains $n$ positive integers $w_i$, representing the values on the power cards.

The third line contains $n$ positive integers $w_i$, representing the values on the attack cards.

Output

Output $T$ lines, each containing a non-negative integer representing the answer for each test case.

Examples

Input 1

2
2 3 2
2 3
1 2
10 16 14
2 3 4 5 6 7 8 9 10 11
1 2 3 4 5 6 7 8 9 10

Output 1

19
253973805

Note 1

For example, if Karen draws attack cards $\{1, 2\}$ and a power card $\{3\}$, the optimal strategy is to play the power card $3$ first, which changes the attack card values to $\{3, 6\}$, and then play the $6$.

Subtasks

For all data, $1\leq k\leq m\leq 2n\leq 3\times 10^3$, and $1\leq w_i\leq 10^8$.

It is guaranteed that the numbers on all power cards are greater than 1.

Let $(\sum 2n)$ denote the sum of $2n$ over all test cases in the input.

For $10\%$ of the data, $1\leq \sum 2n\leq 10$.

For $20\%$ of the data, $1\leq \sum 2n\leq 100$.

For $30\%$ of the data, $1\leq \sum 2n\leq 500$.

Another $20\%$ of the data satisfies the condition that all attack cards have the same value.

Another $20\%$ of the data satisfies $m=k$.

For $100\%$ of the data, $1\leq \sum 2n\leq 3000$.