Crossed Matchings

Time limit1sMemory limit128 MB

Summary

Given two rows of positive integers, draw the maximum number of equal-value matching segments between the rows so that each segment crosses exactly one other and no number is used twice.

Level: Hard8 of 10
Topics: Dynamic programming, Array, Two pointers, Combinatorics
Solved: No attempts yet

Problem

Positive integers are listed in two rows. If two equal numbers lie in different rows — one in the first row and the other in the second row — we may connect them with a single line segment. If the value of such a segment is $r$ , we call it an $r$ -matching segment. The figure below shows a 3-matching segment and a 2-matching segment.

For the given input, we want to draw as many matching segments as possible so that all of the following hold:

Every $a$ -matching segment must cross exactly one $b$ -matching segment, where $a \neq b$ .
No number may be an endpoint of more than one segment (each number is used by at most one segment). For example, the matchings shown below are not allowed.

Write a program that computes the maximum number of matching segments. Note that this number is always even.

Input

The first line contains the number of test cases $M$ ( $1 \le M \le 10$ ). Each test case consists of three lines. The first line contains $N_1$ and $N_2$ , the number of integers in the first and the second row, respectively. The next line contains the $N_1$ integers of the first row, and the following line contains the $N_2$ integers of the second row. All numbers are positive integers less than $100$ .

Output

For each test case, print the maximum number of matching segments on its own line.

Examples4

Example 1

Input

3
6 6
1 3 1 3 1 3
3 1 3 1 3 1
4 4
1 1 3 3 
1 1 3 3 
12 11
1 2 3 3 2 4 1 5 1 3 5 10
3 1 2 3 2 4 12 1 5 5 3

Expected output

6
0
8

Example 2
Input
```
1
2 2
1 2
2 1
```
Expected output
```
2
```
Example 3
Input
```
1
3 3
1 2 3
1 2 3
```
Expected output
```
0
```
Example 4
Input
```
1
3 3
5 6 7
1 2 3
```
Expected output
```
0
```