Wavel Sequence

Problem 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).

Source

2017 Multi-University Training Contest - Team 4

https://acm.hdu.edu.cn/showproblem.php?pid=6078