시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 256 MB65885166841120423.969%

문제

이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다.

학생들이(s1, s2, ..., sr)이라 할 때, r=1이고 s1이 s1을 선택하는 경우나, s1이 s2를 선택하고, s2가 s3를 선택하고,..., sr-1이 sr을 선택하고, sr이 s1을 선택하는 경우에만 한 팀이 될 수 있다.

예를 들어, 한 반에 7명의 학생이 있다고 하자. 학생들을 1번부터 7번으로 표현할 때, 선택의 결과는 다음과 같다.

1 2 3 4 5 6 7
3 1 3 7 3 4 6

위의 결과를 통해 (3)과 (4, 7, 6)이 팀을 이룰 수 있다. 1, 2, 5는 어느 팀에도 속하지 않는다.

주어진 선택의 결과를 보고 어느 프로젝트 팀에도 속하지 않는 학생들의 수를 계산하는 프로그램을 작성하라.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫 줄에는 학생의 수가 정수 n (2 ≤ n ≤ 100,000)으로 주어진다. 각 테스트 케이스의 둘째 줄에는 선택된 학생들의 번호가 주어진다. (모든 학생들은 1부터 n까지 번호가 부여된다.)

출력

각 테스트 케이스마다 한 줄에 출력하고, 각 줄에는 프로젝트 팀에 속하지 못한 학생들의 수를 나타내면 된다.

예제 입력 1

2
7
3 1 3 7 3 4 6
8
1 2 3 4 5 6 7 8

예제 출력 1

3
0
W3sicHJvYmxlbV9pZCI6Ijk0NjYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQxNDAgXHVkNTA0XHViODVjXHVjODFkXHVkMmI4IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM3NzRcdWJjODggXHVhYzAwXHVjNzQ0XHVkNTU5XHVhZTMwXHVjNWQwICYjMzk7XHViYjM4XHVjODFjIFx1ZDU3NFx1YWNiMCYjMzk7IFx1YWMxNVx1Yzc1OFx1Yjk3YyBcdWMyZTBcdWNjYWRcdWQ1NWMgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzQwJm5ic3A7XHVkMTQwIFx1ZDUwNFx1Yjg1Y1x1YzgxZFx1ZDJiOFx1Yjk3YyBcdWMyMThcdWQ1ODlcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWQ1MDRcdWI4NWNcdWM4MWRcdWQyYjggXHVkMzAwXHVjNmQwIFx1YzIxOFx1YzVkMFx1YjI5NCBcdWM4MWNcdWQ1NWNcdWM3NzQgXHVjNWM2XHViMmU0LiBcdWMyZWNcdWM5YzBcdWM1YjQgXHViYWE4XHViNGUwIFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc3NCBcdWIzZDlcdWM3N2NcdWQ1NWMgXHVkMzAwXHVjNzU4IFx1ZDMwMFx1YzZkMFx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM2NDAmbmJzcDtcdWFjMTlcdWM3NzQmbmJzcDtcdWQ1NWMgXHVkMzAwXHViOWNjIFx1Yzc4OFx1Yzc0NCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LiBcdWQ1MDRcdWI4NWNcdWM4MWRcdWQyYjggXHVkMzAwXHVjNzQ0IFx1YWQ2Y1x1YzEzMVx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQsJm5ic3A7XHViYWE4XHViNGUwIFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc0MCBcdWQ1MDRcdWI4NWNcdWM4MWRcdWQyYjhcdWI5N2MgXHVkNTY4XHVhZWQ4XHVkNTU4XHVhY2UwIFx1YzJmNlx1Yzc0MCZuYnNwO1x1ZDU1OVx1YzBkZFx1Yzc0NCZuYnNwO1x1YzEyMFx1ZDBkZFx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIChcdWIyZTgsIFx1YjJlOCBcdWQ1NWMgXHViYTg1XHViOWNjIFx1YzEyMFx1ZDBkZFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LikmbmJzcDtcdWQ2M2NcdWM3OTAgXHVkNTU4XHVhY2UwIFx1YzJmNlx1YzViNFx1ZDU1OFx1YjI5NCBcdWQ1NTlcdWMwZGRcdWM3NDAgXHVjNzkwXHVhZTMwIFx1Yzc5MFx1YzJlMFx1Yzc0NCBcdWMxMjBcdWQwZGRcdWQ1NThcdWIyOTQgXHVhYzgzXHViM2M0IFx1YWMwMFx1YjJhNVx1ZDU1OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTU5XHVjMGRkXHViNGU0XHVjNzc0KHM8c3ViPjE8XC9zdWI+LCBzPHN1Yj4yPFwvc3ViPiwgLi4uLCBzPHN1Yj5yPFwvc3ViPilcdWM3NzRcdWI3N2MgXHVkNTYwIFx1YjU0YywmbmJzcDtyPTFcdWM3NzRcdWFjZTAgczxzdWI+MTxcL3N1Yj5cdWM3NzQgczxzdWI+MTxcL3N1Yj5cdWM3NDQgXHVjMTIwXHVkMGRkXHVkNTU4XHViMjk0IFx1YWNiZFx1YzZiMFx1YjA5OCwgczxzdWI+MTxcL3N1Yj5cdWM3NzQgczxzdWI+MjxcL3N1Yj5cdWI5N2MgXHVjMTIwXHVkMGRkXHVkNTU4XHVhY2UwLCBzPHN1Yj4yPFwvc3ViPlx1YWMwMCBzPHN1Yj4zPFwvc3ViPlx1Yjk3YyBcdWMxMjBcdWQwZGRcdWQ1NThcdWFjZTAsLi4uLCBzPHN1Yj5yLTE8XC9zdWI+XHVjNzc0IHM8c3ViPnI8XC9zdWI+XHVjNzQ0IFx1YzEyMFx1ZDBkZFx1ZDU1OFx1YWNlMCwgczxzdWI+cjxcL3N1Yj5cdWM3NzQgczxzdWI+MTxcL3N1Yj5cdWM3NDQgXHVjMTIwXHVkMGRkXHVkNTU4XHViMjk0IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjljYyBcdWQ1NWMgXHVkMzAwXHVjNzc0IFx1YjQyMCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWQ1NWMgXHViYzE4XHVjNWQwIDdcdWJhODVcdWM3NTggXHVkNTU5XHVjMGRkXHVjNzc0IFx1Yzc4OFx1YjJlNFx1YWNlMCBcdWQ1NThcdWM3OTAuIFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc0NCAxXHViYzg4XHViZDgwXHVkMTMwIDdcdWJjODhcdWM3M2NcdWI4NWMgXHVkNDVjXHVkNjA0XHVkNTYwIFx1YjU0YywgXHVjMTIwXHVkMGRkXHVjNzU4IFx1YWNiMFx1YWNmY1x1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48dGFibGUgY2xhc3M9XCJ0YWJsZSB0YWJsZS1ib3JkZXJlZFwiIHN0eWxlPVwid2lkdGg6MzAlXCI+XHJcblx0PHRoZWFkPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGg+MTxcL3RoPlxyXG5cdFx0XHQ8dGg+MjxcL3RoPlxyXG5cdFx0XHQ8dGg+MzxcL3RoPlxyXG5cdFx0XHQ8dGg+NDxcL3RoPlxyXG5cdFx0XHQ8dGg+NTxcL3RoPlxyXG5cdFx0XHQ8dGg+NjxcL3RoPlxyXG5cdFx0XHQ8dGg+NzxcL3RoPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGhlYWQ+XHJcblx0PHRib2R5PlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+MzxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MzxcL3RkPlxyXG5cdFx0XHQ8dGQ+NzxcL3RkPlxyXG5cdFx0XHQ8dGQ+MzxcL3RkPlxyXG5cdFx0XHQ8dGQ+NDxcL3RkPlxyXG5cdFx0XHQ8dGQ+NjxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGJvZHk+XHJcbjxcL3RhYmxlPlxyXG5cclxuPHA+XHVjNzA0XHVjNzU4IFx1YWNiMFx1YWNmY1x1Yjk3YyBcdWQxYjVcdWQ1NzQgKDMpXHVhY2ZjICg0LCA3LCA2KVx1Yzc3NCBcdWQzMDBcdWM3NDQgXHVjNzc0XHViOGYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIDEsIDIsIDVcdWIyOTQgXHVjNWI0XHViMjkwIFx1ZDMwMFx1YzVkMFx1YjNjNCBcdWMxOGRcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM4ZmNcdWM1YjRcdWM5YzQgXHVjMTIwXHVkMGRkXHVjNzU4IFx1YWNiMFx1YWNmY1x1Yjk3YyBcdWJjZjRcdWFjZTAgXHVjNWI0XHViMjkwIFx1ZDUwNFx1Yjg1Y1x1YzgxZFx1ZDJiOCBcdWQzMDBcdWM1ZDBcdWIzYzQgXHVjMThkXHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NCBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NTggXHVjMjE4XHViOTdjIFx1YWNjNFx1YzBiMFx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHViNzdjLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQ1NTlcdWMwZGRcdWM3NTggXHVjMjE4XHVhYzAwIFx1YzgxNVx1YzIxOCZuYnNwO24gKDIgJmxlOyBuJm5ic3A7JmxlOyAxMDAsMDAwKVx1YzczY1x1Yjg1YyZuYnNwO1x1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCZuYnNwO1x1YzEyMFx1ZDBkZFx1YjQxYyBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NTggXHViYzg4XHVkNjM4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDsoXHViYWE4XHViNGUwIFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc0MCAxXHViZDgwXHVkMTMwIG5cdWFlNGNcdWM5YzAgXHViYzg4XHVkNjM4XHVhYzAwIFx1YmQ4MFx1YzVlY1x1YjQxY1x1YjJlNC4pPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWNkOWNcdWI4MjVcdWQ1NThcdWFjZTAsIFx1YWMwMSBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkNTA0XHViODVjXHVjODFkXHVkMmI4IFx1ZDMwMFx1YzVkMCBcdWMxOGRcdWQ1NThcdWM5YzAgXHViYWJiXHVkNTVjIFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc1OCBcdWMyMThcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViYTc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI5NDY2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVGVybSBQcm9qZWN0IiwiZGVzY3JpcHRpb24iOiI8cD5TdHVkZW50cyB3aG8gZW5yb2xsZWQgaW4gdGhlICZsc3F1bztQcm9ibGVtIFNvbHZpbmcmcnNxdW87IGNvdXJzZSBpbiB0aGlzIGZhbGwgc2VtZXN0ZXIgaGF2ZSB0byBjYXJyeSBvdXQgYSB0ZXJtIHByb2plY3QuIFRoZXJlIGlzIG5vIGxpbWl0IHRvIHRoZSBudW1iZXIgb2YgcHJvamVjdCB0ZWFtIG1lbWJlcnMuIEV2ZW4gb25lIHRlYW0gaXMgYWxsb3dlZCBzdWNoIHRoYXQgYWxsIHN0dWRlbnRzIGFyZSBtZW1iZXJzIG9mIHRoZSBzYW1lIHRlYW0uIEluIG9yZGVyIHRvIGZvcm0gcHJvamVjdCB0ZWFtcywgZXZlcnkgc3R1ZGVudCBzaG91bGQgc2VsZWN0IGEgZnJpZW5kIHdpdGggd2hvbSBoZSBvciBzaGUgd2FudHMgdG8gd29yay4gQSBzdHVkZW50IHdobyB3YW50cyB0byB3b3JrIGFsb25lIGNhbiBzZWxlY3QgaGltc2VsZiBvciBoZXJzZWxmLiBBIHN0dWRlbnQgbGlzdCAoczxzdWI+MTxcL3N1Yj4sIHM8c3ViPjI8XC9zdWI+LCAuLi4sIHM8c3ViPnI8XC9zdWI+KSBjYW4gYmUgYSB0ZWFtIGlmIGVpdGhlciByPTEgYW5kIHM8c3ViPjE8XC9zdWI+IHNlbGVjdHMgczxzdWI+MTxcL3N1Yj4gb3IgczxzdWI+MTxcL3N1Yj4gc2VsZWN0cyBzPHN1Yj4yPFwvc3ViPiwgczxzdWI+MjxcL3N1Yj4gc2VsZWN0cyBzPHN1Yj4zPFwvc3ViPiwgJmhlbGxpcDsgLCBzPHN1Yj5yLTE8XC9zdWI+IHNlbGVjdHMgczxzdWI+cjxcL3N1Yj4sIGFuZCBzPHN1Yj5yPFwvc3ViPiZuYnNwO3NlbGVjdHMgczxzdWI+MTxcL3N1Yj4uPFwvcD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCBsZXQmcnNxdW87cyBhc3N1bWUgdGhhdCB0aGVyZSBhcmUgNyBzdHVkZW50cyBpbiB0aGUgY2xhc3MuIFRoZSBzdHVkZW50cyBhcmUgbnVtYmVyZWQgZnJvbSAxIHRvIDcuIFRoZSBmb2xsb3dpbmcgaXMgdGhlIHJlc3VsdCBvZiB0aGUgc2VsZWN0aW9uLjxcL3A+XHJcblxyXG48dGFibGUgY2xhc3M9XCJ0YWJsZSB0YWJsZS1ib3JkZXJlZFwiIHN0eWxlPVwid2lkdGg6MzAlXCI+XHJcblx0PHRoZWFkPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGg+MTxcL3RoPlxyXG5cdFx0XHQ8dGg+MjxcL3RoPlxyXG5cdFx0XHQ8dGg+MzxcL3RoPlxyXG5cdFx0XHQ8dGg+NDxcL3RoPlxyXG5cdFx0XHQ8dGg+NTxcL3RoPlxyXG5cdFx0XHQ8dGg+NjxcL3RoPlxyXG5cdFx0XHQ8dGg+NzxcL3RoPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGhlYWQ+XHJcblx0PHRib2R5PlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+MzxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MzxcL3RkPlxyXG5cdFx0XHQ8dGQ+NzxcL3RkPlxyXG5cdFx0XHQ8dGQ+MzxcL3RkPlxyXG5cdFx0XHQ8dGQ+NDxcL3RkPlxyXG5cdFx0XHQ8dGQ+NjxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGJvZHk+XHJcbjxcL3RhYmxlPlxyXG5cclxuPHA+RnJvbSB0aGUgYWJvdmUgcmVzdWx0LCB3ZSBjYW4gc2VlIHRoYXQgdHdvIHRlYW1zICgzKSBhbmQgKDQsIDcsIDYpIGFyZSBmb3JtZWQuIFN0dWRlbnRzIDEsIDIsIGFuZCA1IGRvbiZyc3F1bzt0IGJlbG9uZyB0byBhbnkgdGVhbS48XC9wPlxyXG5cclxuPHA+R2l2ZW4gdGhlIHJlc3VsdCBvZiB0aGUgc2VsZWN0aW9uLCB3cml0ZSBhIHByb2dyYW0gdG8gY29tcHV0ZSB0aGUgbnVtYmVyIG9mIHN0dWRlbnRzIHdobyBkb24mcnNxdW87dCBiZWxvbmcgdG8gYSBwcm9qZWN0IHRlYW0uJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gcmVhZCBmcm9tIHN0YW5kYXJkIGlucHV0LiBUaGUgaW5wdXQgY29uc2lzdHMgb2YgVCB0ZXN0IGNhc2VzLiBUaGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMgVCBpcyBnaXZlbiBpbiB0aGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQuIEVhY2ggdGVzdCBjYXNlIHN0YXJ0cyB3aXRoIGEgbGluZSBjb250YWluaW5nIGFuIGludGVnZXIgbiAoMiAmbGU7IG4gJmxlOyAxMDAgMDAwKSwgd2hlcmUgbiBpcyB0aGUgbnVtYmVyIG9mIHN0dWRlbnRzIGluIHRoZSBjbGFzcy4gQWxsIHN0dWRlbnRzIGFyZSBudW1iZXJlZCBmcm9tIDEgdG8gbi4gVGhlIG5leHQgbGluZSBvZiBlYWNoIHRlc3QgY2FzZSBjb250YWlucyBuIGludGVnZXJzIHM8c3ViPjE8XC9zdWI+LCBzPHN1Yj4yPFwvc3ViPiwgLi4uLCBzPHN1Yj5uPFwvc3ViPiwgd2hlcmUgczxzdWI+aTxcL3N1Yj4mbmJzcDtpcyB0aGUgc3R1ZGVudCB3aG8gd2FzIGEgc3R1ZGVudCBcdTA3NDUgc2VsZWN0ZWQgYnkuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHdyaXRlIHRvIHN0YW5kYXJkIG91dHB1dC4gUHJpbnQgZXhhY3RseSBvbmUgbGluZSBmb3IgZWFjaCB0ZXN0IGNhc2UuIFRoZSBsaW5lIHNob3VsZCBjb250YWluIHRoZSBudW1iZXIgb2Ygc3R1ZGVudHMgd2hvIGRvbiZyc3F1bzt0IGJlbG9uZyB0byBhIHByb2plY3QgdGVhbS4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

ICPC > Regionals > Asia Pacific > Korea > Asia Regional - Daejeon 2013 L번