Merged LIS ~ Multiplex Coder

You have two arrays

$A$ and $B$ of size $N$ and $M$ respectively. You have to merge both the arrays to form a new array $C$ of size $N + M$ (the relative order of elements in the original arrays $A$ and $B$ should not change in the array $C$ ).

For e.g. if $A = [1, 2, 7]$ and $B = [3, 6, 5]$ , one possible way to merge them to form $C$ is: $C = [1, 3, 6, 2, 5, 7]$ .

Maximize the length of longest non-decreasing subsequence of the merged array $C$ .

As a reminder, a non-decreasing subsequence of some array $X$ is a sequence of indices $i_{1}, i_{2}, . . ., i_{k}$ , such that $i_{1} < i_{2} < . . . < i_{k}$ and $X_{i_{1}} \leq X_{i_{2}} \leq . . . \leq X_{i_{k}}$

Input Format

The first line contains $T$ - the number of test cases. Then the test cases follow.
The first line of each test case contains two integers $N$ and $M$ - the size of the array $A$ and $B$ respectively.
The second line of each test case contains $N$ space-separated integers $A_{1}, A_{2}, \dots, A_{N}$ denoting the array $A$ .
The third line of each test case contains $M$ space-separated integers $B_{1}, B_{2}, \dots, B_{M}$ denoting the array $B$ .

Output Format

For each test case, output the maximum possible length of longest non-decreasing subsequence in the merged array.

Constraints

$1 \leq T \leq 1000$
$1 \leq N, M \leq 10^{5}$
$1 \leq A_{i}, B_{i} \leq 10^{9}$
It is guaranteed that the sum of $N$ over all test cases does not exceed $4 \cdot 10^{5}$ .
It is guaranteed that the sum of $M$ over all test cases does not exceed $4 \cdot 10^{5}$ .

Sample Input 1

Sample Output 1

4
5

Explanation

Test Case-1: We can merge the arrays in the following way: $C = [6, 1, 3, 4, 5]$ . The length of longest non-decreasing subsequence in this case is $4$ .

Test Case-2: We can merge the arrays in the following way: $C = [1, 2, 2, 3, 4]$ . The length of longest non-decreasing subsequence in this case is $5$ .

Merged LIS