Under construction

Still being built. Things may change

Cancel the Trains

Time limit1sMemory limit512 MB

Summary
Given two sorted lists of train numbers, count how many numbers appear in both, since only trains with the same number can crash.
Level

Easy2 of 10

Topics
Array, Two pointers
Solved
No attempts yet

Problem

Gildong's town has a train system with 100100 trains that travel from the bottom end to the top end and 100100 trains that travel from the left end to the right end. The trains starting from each side are numbered from 11 to 100100, and all trains have the same speed. Look at the picture below.

The train system can be represented as coordinates on a 2D plane. The ii-th train starting at the bottom end is initially at (i,0)(i,0) and will be at (i,T)(i,T) after TT minutes. The ii-th train starting at the left end is initially at (0,i)(0,i) and will be at (T,i)(T,i) after TT minutes. All trains arrive at their destinations after 101101 minutes.

Gildong found that some trains scheduled to depart at the same time are very dangerous. At this time, nn trains are scheduled to depart from the bottom end and mm trains from the left end. If two trains are both at (x,y)(x,y) at the same time for some xx and yy, they crash. Find the minimum number of trains that must be cancelled to prevent all crashes.

Input

The first line contains the number of test cases tt (1≤t≤1001\le t\le 100).

Each test case has three lines. The first line contains two integers nn and mm (1≤n,m≤1001\le n,m\le 100), the number of trains departing from the bottom end and the left end. The second line contains nn integers, the train numbers departing from the bottom end. The third line contains mm integers, the train numbers departing from the left end. Each number is between 11 and 100100, inclusive, and the numbers are given in strictly increasing order.

Output

For each test case, print one integer: the minimum number of trains to cancel to prevent all crashes.

Hint

In the first case, no crash occurs if the current schedule is followed, so the answer is zero.

In the second case, a crash occurs at T=4T=4, as shown in the picture below. Cancelling one of these trains leaves the remaining trains with no crashes, so the answer is one.

Examples1

  1. Example 1

    Input
    3
    1 2
    1
    3 4
    3 2
    1 3 4
    2 4
    9 14
    2 7 16 28 33 57 59 86 99
    3 9 14 19 25 26 28 35 41 59 85 87 99 100
    
    Expected output
    0
    1
    3