#930 Sequence Operations

Statement

Statement language

There are an integer sequence $A$ of length $N$ and an integer sequence $B$ of length $M$ .

You may perform the following operation zero or more times, in any order.

Let $n$ be the length of the current sequence $X$ . Choose a position $i$ ( $1\le i\le n$ ). For every $j$ (), simultaneously add to , and then remove . The remaining elements keep their order and are renumbered.

This operation can be performed on $A$ or $B$ .

If the last element is chosen, only that element is removed. There is no restriction on the values of the elements during the operations.

Find the minimum number of operations needed to make the two sequences equal in length and in all elements. Two empty sequences are also considered equal. The number of operations is the total number of operations performed on both sequences.

Input

The input is given in the following format.

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

Output

For each test case, output the minimum number of operations on a single line.

Constraints

$1\le T\le5000$ .
$1\le N,M\le5000$ .
$- 5000 \leq A_{i} \leq$ ().

Subtasks

#	Score	Constraints
1	8	$N,M\le8$ , $\sum N,\sum M\le300$ .
2	22	; .

Samples

Input

Output

1
0
2