시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1015 708 653 72.475%

문제

이번 ACM-ICPC 대회의 자리는 참가자들이 직접 정한다. 참가자들은 예비 소집일에 자신이 원하는 자리를 미리 정해놓았고, 대회 당일에 어제 적어놓은 자리에 앉으면 된다. 여러명이 같은 자리를 적어논 경우에는, 먼저 도착한 사람이 그 자리에 앉게되고, 앉지 못한 사람은 대회에 참가할 수 없다.

각 사람이 선호하는 자리가 주어졌을 때, 대회에 참가하지 못하는 사람의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스는 다음과 같이 구성되어 있다.

첫째 줄에 참가자의 수 P와 자리의 수 M이 주어진다. (1 ≤ P, M ≤ 500) 다음 P개 줄에는 각 참가자가 원하는 자리가 주어진다. 자리는 1번부터 M번까지 있다. 입력으로 주어지는 참가자가 도착하는 순서이다.

출력

각 테스트 케이스에 대해서, 대회에 참가하지 못하는 사람의 수를 출력한다.

예제 입력 1

3
4 1
1
1
1
1
4 4
1
2
3
4
4 4
1
4
1
4

예제 출력 1

3
0
2
W3sicHJvYmxlbV9pZCI6IjUxNzYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIzMDBcdWQ2OGMgXHVjNzkwXHViOWFjIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWM3NzRcdWJjODggQUNNLUlDUEMgXHViMzAwXHVkNjhjXHVjNzU4IFx1Yzc5MFx1YjlhY1x1YjI5NCBcdWNjMzhcdWFjMDBcdWM3OTBcdWI0ZTRcdWM3NzQgXHVjOWMxXHVjODExIFx1YzgxNVx1ZDU1Y1x1YjJlNC4gXHVjYzM4XHVhYzAwXHVjNzkwXHViNGU0XHVjNzQwIFx1YzYwOFx1YmU0NCBcdWMxOGNcdWM5ZDFcdWM3N2NcdWM1ZDAgXHVjNzkwXHVjMmUwXHVjNzc0IFx1YzZkMFx1ZDU1OFx1YjI5NCBcdWM3OTBcdWI5YWNcdWI5N2MgXHViYmY4XHViOWFjIFx1YzgxNVx1ZDU3NFx1YjE5M1x1YzU1OFx1YWNlMCwgXHViMzAwXHVkNjhjIFx1YjJmOVx1Yzc3Y1x1YzVkMCBcdWM1YjRcdWM4MWMgXHVjODAxXHVjNWI0XHViMTkzXHVjNzQwIFx1Yzc5MFx1YjlhY1x1YzVkMCBcdWM1NDlcdWM3M2NcdWJhNzQgXHViNDFjXHViMmU0LiBcdWM1ZWNcdWI3ZWNcdWJhODVcdWM3NzQgXHVhYzE5XHVjNzQwIFx1Yzc5MFx1YjlhY1x1Yjk3YyBcdWM4MDFcdWM1YjRcdWIxN2MgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0LCBcdWJhM2NcdWM4MDAgXHViM2M0XHVjYzI5XHVkNTVjIFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWFkZjggXHVjNzkwXHViOWFjXHVjNWQwIFx1YzU0OVx1YWM4Y1x1YjQxOFx1YWNlMCwgXHVjNTQ5XHVjOWMwIFx1YmFiYlx1ZDU1YyBcdWMwYWNcdWI3OGNcdWM3NDAgXHViMzAwXHVkNjhjXHVjNWQwIFx1Y2MzOFx1YWMwMFx1ZDU2MCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWFjMDEgXHVjMGFjXHViNzhjXHVjNzc0IFx1YzEyMFx1ZDYzOFx1ZDU1OFx1YjI5NCBcdWM3OTBcdWI5YWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHViMzAwXHVkNjhjXHVjNWQwIFx1Y2MzOFx1YWMwMFx1ZDU1OFx1YzljMCBcdWJhYmJcdWQ1NThcdWIyOTQgXHVjMGFjXHViNzhjXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggS1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVhZDZjXHVjMTMxXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWNjMzhcdWFjMDBcdWM3OTBcdWM3NTggXHVjMjE4IFBcdWM2NDAgXHVjNzkwXHViOWFjXHVjNzU4IFx1YzIxOCBNXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBQLCBNICZsZTsgNTAwKSBcdWIyZTRcdWM3NGMgUFx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1Y2MzOFx1YWMwMFx1Yzc5MFx1YWMwMCBcdWM2ZDBcdWQ1NThcdWIyOTQgXHVjNzkwXHViOWFjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzkwXHViOWFjXHViMjk0IDFcdWJjODhcdWJkODBcdWQxMzAgTVx1YmM4OFx1YWU0Y1x1YzljMCBcdWM3ODhcdWIyZTQuIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgXHVjYzM4XHVhYzAwXHVjNzkwXHVhYzAwIFx1YjNjNFx1Y2MyOVx1ZDU1OFx1YjI5NCBcdWMyMWNcdWMxMWNcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWIzMDBcdWQ2OGNcdWM1ZDAgXHVjYzM4XHVhYzAwXHVkNTU4XHVjOWMwIFx1YmFiYlx1ZDU1OFx1YjI5NCBcdWMwYWNcdWI3OGNcdWM3NTggXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI1MTc2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ29udGVzdCBTZWF0aW5nIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgcGFydGljaXBhbnRzIHN0YXJ0IGFycml2aW5nLCBhcmUgdGFraW5nIHNlYXRzIGF0IHRoZSBjb21wdXRlcnMuIEFmdGVyIHByYWN0aWNpbmcgYSBiaXQsIG1hbnkgb2YgdGhlbSBsZWF2ZSB0ZW1wb3JhcmlseSBpbiBvcmRlciB0byBncmFiIHNvbWUgc25hY2tzLiBPZiBjb3Vyc2UsIHRoaXMgc29tZXRpbWVzIHJlc3VsdHMgaW4gYSBuZXcgcGFydGljaXBhbnQgdHJ5aW5nIHRvIHVzZSBhbiBhbHJlYWR5IGNsYWltZWQgY29tcHV0ZXIuIFdlIHdhbnQgdG8gXHVmYjAxZ3VyZSBvdXQganVzdCBob3cgb2Z0ZW4gdGhpcyBoYXBwZW5zLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIFx1ZmIwMXJzdCBsaW5lIHdpbGwgY29udGFpbiB0aGUgbnVtYmVyIEsgb2YgaW5wdXQgZGF0YSBzZXRzLiBUaGlzIGlzIGZvbGxvd2VkIGJ5IHRoZSBLIGRhdGEgc2V0cywgZWFjaCBvZiB0aGUgZm9sbG93aW5nIGZvcm1hdDo8XC9wPlxyXG5cclxuPHA+VGhlIFx1ZmIwMXJzdCBsaW5lIGNvbnRhaW5zIHR3byBudW1iZXJzIFAgYW5kIE0sIHRoZSBudW1iZXIgb2YgcGFydGljaXBhbnRzICgxICZsZTsgUCAmbGU7IDUwMCksIGFuZCB0aGUgbnVtYmVyIG9mIG1hY2hpbmVzICgxICZsZTsgTSAmbGU7IDUwMCkuIFRoaXMgaXMgZm9sbG93ZWQgYnkgUCBsaW5lcywgZWFjaCBjb250YWluaW5nIGFuIGludGVnZXIgYmV0d2VlbiAxIGFuZCBNLCB0aGUgbnVtYmVyIG9mIHRoZSBtYWNoaW5lIHRoYXQgdGhlIHBhcnRpY2lwYW50IGlzIHRyeWluZyB0byBzaXQgZG93biBhdCBcdWZiMDFyc3QuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggZGF0YSBzZXQsIFx1ZmIwMXJzdCBvdXRwdXQgaXRzIG51bWJlciwgdGhlbiBpbiBhIG5ldyBsaW5lIHRoZSB0b3RhbCBudW1iZXIgb2YgdW5zdWNjZXNzZnVsIHNpdHRpbmcgYXR0ZW1wdHMuIEFuIGF0dGVtcHQgaXMgdW5zdWNjZXNzZnVsIGlmIGJ5IHRoZSB0aW1lIHBhcnRpY2lwYW50IGkgaXMgdHJ5aW5nIHRvIHNpdCBhdCBtYWNoaW5lIGosIHNvbWUgb3RoZXIgcGFydGljaXBhbnQgaGFzIGFscmVhZHkgc2F0IGF0IG1hY2hpbmUgai48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

University > The USC Programming Contest > Fall 2007 B번