Box Factory (Large)

You own a factory with two assembly lines. The first line makes boxes and the second line makes toys to put in those boxes. Every box and every toy carries a type number, and a toy fits a box only when the two type numbers are equal.

You start by picking up a box from the first line and a toy from the second line. After that you repeat the following actions as often as you like.

• Throw out the box you are holding and pick up the next box.
• Throw out the toy you are holding and pick up the next toy.
• If the box and the toy have the same type, put the toy in the box, send it out to customers, then pick up the next box and the next toy.

You always pick boxes up in the order in which they are made, and the same holds for toys. You know the order in which both lines produce. Plan a strategy that sends out as many boxed toys as possible, and report that largest number.

The two lines make a lot of boxes and toys. They tend to make one kind of thing for a long time before switching.

The first line of input contains the number of test cases $T$.

Each test case begins with a line containing two integers $N$ and $M$. The next line contains $2N$ integers $a_1, A_1, a_2, A_2, \dots, a_N, A_N$, and the line after that contains $2M$ integers $b_1, B_1, b_2, B_2, \dots, b_M, B_M$.

The first assembly line makes $a_1$ boxes of type $A_1$, then $a_2$ boxes of type $A_2$, and so on until it finishes with $a_N$ boxes of type $A_N$. The second assembly line makes $b_1$ toys of type $B_1$ through $b_M$ toys of type $B_M$ in the same way. Two neighbouring runs may share a type number.

Limits

• $1 \le T \le 100$
• $1 \le a_i, b_i \le 10^{16}$
• $1 \le A_i, B_i \le 100$
• $1 \le N, M \le 100$

For each test case, output one line in the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the largest number of boxed toys you can send out to customers.