Wavel Sequence

Time Limit: 4000/2000 MS (Java/Others)

Memory Limit: 524288/524288 K (Java/Others)

Description

Have you ever seen the wave? It's a wonderful view of nature. Little Q is attracted to such wonderful thing, he even likes everything that looks like wave. Formally, he defines a sequence $a_1,a_2,...,a_n$ as ''wavel'' if and only if $a_1<a_2>a_3<a_4>a_5<a_6...$



Picture from Wikimedia Commons


Now given two sequences $a_1,a_2,...,a_n$ and $b_1,b_2,...,b_m$, Little Q wants to find two sequences $f_1,f_2,...,f_k(1\leq f_i\leq n,f_i<f_{i+1})$ and $g_1,g_2,...,g_k(1\leq g_i\leq m,g_i<g_{i+1})$, where $a_{f_i}=b_{g_i}$ always holds and sequence $a_{f_1},a_{f_2},...,a_{f_k}$ is ''wavel''.

Moreover, Little Q is wondering how many such two sequences $f$ and $g$ he can find. Please write a program to help him figure out the answer.

Input

The first line of the input contains an integer $T(1\leq T\leq15)$, denoting the number of test cases.

In each test case, there are $2$ integers $n,m(1\leq n,m\leq 2000)$ in the first line, denoting the length of $a$ and $b$.

In the next line, there are $n$ integers $a_1,a_2,...,a_n(1\leq a_i\leq 2000)$, denoting the sequence $a$.

Then in the next line, there are $m$ integers $b_1,b_2,...,b_m(1\leq b_i\leq 2000)$, denoting the sequence $b$.

Output

For each test case, print a single line containing an integer, denoting the answer. Since the answer may be very large, please print the answer modulo $998244353$.

Sample Input

1 3 5 1 5 3 4 1 1 5 3

Sample Output

10
Hint
(1)f=(1),g=(2). (2)f=(1),g=(3). (3)f=(2),g=(4). (4)f=(3),g=(5). (5)f=(1,2),g=(2,4). (6)f=(1,2),g=(3,4). (7)f=(1,3),g=(2,5). (8)f=(1,3),g=(3,5). (9)f=(1,2,3),g=(2,4,5). (10)f=(1,2,3),g=(3,4,5).

Hint

liuyiding

Source

2017 Multi-University Training Contest - Te

提交代码