A. Cancel the Trains

60 阅读 0 评论 40 点赞

我是靠谱客的博主独特钢笔，最近开发中收集的这篇文章主要介绍A. Cancel the Trains，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

time limit per test

1 second

memory limit per test

512 megabytes

input

standard input

output

standard output

Gildong's town has a train system that has 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, respectively, and all trains have the same speed. Let's take a 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, and 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.

However, Gildong found that some trains scheduled to depart at a specific time, simultaneously, are very dangerous. At this time, nn trains are scheduled to depart from the bottom end and mm trains are scheduled to depart from the left end. If two trains are both at (x,y)(x,y) at the same time for some xx and yy, they will crash into each other. Therefore, he is asking you to find the minimum number of trains that should be cancelled to prevent all such crashes.

Input

Each test contains one or more test cases. The first line contains the number of test cases tt (1≤t≤1001≤t≤100).

Each test case contains three lines. The first line of each test case consists of two integers nn and mm (1≤n,m≤1001≤n,m≤100) — the number of trains scheduled to depart from the bottom end, and the number of trains scheduled to depart from the left end, respectively.

The second line of each test case contains nn integers. Each integer is a train number that is scheduled to start from the bottom end. The numbers are given in strictly increasing order, and are between 11 and 100100, inclusive.

The third line of each test case contains mm integers. Each integer is a train number that is scheduled to start from the left end. The numbers are given in strictly increasing order, and are between 11 and 100100, inclusive.

Output

For each test case, print a single integer: the minimum number of trains that should be canceled in order to prevent all crashes.

Example

input

Copy

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

output

Copy

0
1
3

Note

In the first case, we can show that there will be no crashes if the current schedule is followed. Therefore, the answer is zero.

In the second case, at T=4T=4, there will be a crash, as can be seen in the picture below. We can prove that after canceling one of these trains, the remaining trains will not crash. Therefore, the answer is one.

解题说明：水题，看题目的图示，横纵偏移一样的列车必然相撞，统计相同的数字即可。

#include<stdio.h>

int a[101], b[101];
int main()
{
	int t, n, m, i, o, j;
	scanf("%d", &t);
	while (t)
	{
		t--;
		o = 0;
		scanf("%d%d", &n, &m);
		for (i = 1; i <= n; i++)
		{
			scanf("%d", &a[i]);
		}
		for (i = 1; i <= m; i++)
		{
			scanf("%d", &b[i]);
		}
		for (i = 1; i <= n; i++)
		{
			for (j = 1; j <= m; j++)
			{
				if (a[i] == b[j])
				{
					o++;
				}
			}
		}
		printf("%dn", o);
	}
	return 0;
}