신입 사원
면접 대비시간 제한2초메모리 제한256 MB
두 기준으로 순위가 매겨진 지원자들 중 두 순위 모두에서 자신보다 나은 지원자가 없는 사람의 수를 구합니다.
문제
한 회사가 신입 사원을 채용하려고 한다. 지원자는 서류 심사 순위와 면접 순위, 두 가지 순위를 받는다.
회사는 어떤 지원자보다 두 순위가 모두 낮은 지원자는 선발하지 않는다. 다시 말해 지원자 A보다 서류 심사 순위도 높고 면접 순위도 높은 지원자 B가 존재하면, A는 선발될 수 없다.
이 기준을 만족하면서 회사가 선발할 수 있는 신입 사원의 최대 인원수를 구하라.
입력
첫째 줄에 테스트 케이스의 개수 T (1 <= T <= 20)가 주어진다.
각 테스트 케이스의 첫째 줄에는 지원자의 수 N (1 <= N <= 100,000)이 주어진다. 다음 N개 줄에는 각 지원자의 서류 심사 순위와 면접 순위가 공백으로 구분되어 주어진다.
두 순위는 모두 1위부터 N위까지 중복 없이 정해진다. 순위가 작을수록 더 좋은 성적이다.
출력
각 테스트 케이스마다 선발할 수 있는 신입 사원의 최대 인원수를 한 줄에 하나씩 출력한다.