Chiaki 有两个序列 $a_1, a_2, \dots, a_n$ 和 $b_1, b_2, \dots, b_m$。她想要找到它们的最长公共子序列 $c_1, c_2, \dots, c_k$，使得 $c_1 \le c_2 \le \dots \le c_k$。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 10^6$)，表示两个序列的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 3$)。

第三行包含 $m$ 个整数 $b_1, b_2, \dots, b_m$ ($1 \le b_i \le 3$)。

保证所有测试数据中 $\max\{n, m\}$ 的总和不超过 $10^6$。

输出格式

对于每组测试数据，输出一个整数 $k$，表示满足 $c_1 \le c_2 \le \dots \le c_k$ 的最长公共子序列的长度。

样例

样例输入 1

3
3 3
1 2 3
1 2 3
3 3
1 1 1
1 1 2
3 3
1 3 2
1 2 3

样例输出 1

3
2
2