The fist falls on you again. The "fist" is a problem: given two permutations $s$ and $t$ of $1, \dots, n$, find the number of ways to partition $s$ into at most $k$ segments and then perform a merge sort on them such that the resulting sequence is exactly $t$. The answer should be taken modulo $998244353$.

The process of performing a merge sort on several (not necessarily ordered) sequences is defined as follows: in each step, find the minimum value among the heads of all non-empty sequences, append it to the end of the result sequence, and remove it from its original sequence, until all sequences are empty.

Each test case contains multiple datasets.

Input

The first line contains an integer $T$, representing the number of datasets.

For each dataset, the first line contains two integers $n$ and $k$. The next line contains $n$ integers, representing $s$. The next line contains $n$ integers, representing $t$.

Output

A single line containing an integer, representing the answer.

Examples

Input 1

(See ex_sort1.in in the provided files)

Output 1

(See ex_sort1.out in the provided files)

Note

The sample case contains all data satisfying $n = 5$.

Constraints

For all data, it is guaranteed that $1 \le n \le 10^4$ and $\sum n \le 1.2 \times 10^6$. The constraints are strange because the original problem is like that.