Hide

Problem I
Excellent Engineers

You are working for an agency that selects the best software engineers from Belgium, the Netherlands and Luxembourg for employment at various international companies. Given the very large number of excellent software engineers these countries have to offer, the agency has charged you to develop a tool that quickly selects the best candidates available from the agency’s files.

Before a software engineer is included in the agency’s files, he has to undergo extensive testing. Based on these tests, all software engineers are ranked on three essential skills: communication skills, programming skills, and algorithmic knowledge. The software engineer with rank one in the category algorithmic knowledge is the best algorithmic expert in the files, with rank two the second best, etcetera.

For potential customers, your tool needs to process the agency’s files and produce a shortlist of the potentially most interesting candidates. A software engineer is a potential candidate that is to be put on this shortlist if there is no other software engineer in the files that scores better on all three skills. That is, an engineer is to be put on the shortlist if there is no other software engineer that has better communication skills, better programming skills, and more algorithmic knowledge.

\includegraphics[width=0.65\textwidth ]{marketing_interview-125}
Figure 1: source: xkcd.com/125

Input

On the first line one positive number: the number of test cases, at most 100. After that per test case:

  • one line with a single integer $n$ ($1 \leq n \leq 100\, 000$): the number of software engineers in the agency’s files.

  • $n$ lines, each with three space-separated integers $r_1$, $r_2$ and $r_3$ ($1 \leq r_1, r_2, r_3 \leq n$): the rank of each software engineer from the files with respect to his communication skills, programming skills and algorithmic knowledge, respectively.

For each skill $s$ and each rank $x$ between $1$ and $n$, there is exactly one engineer with $r_ s = x$.

Output

Per test case:

  • one line with a single integer: the number of candidates on the shortlist.

Sample Input 1 Sample Output 1
3
3
2 3 2
3 2 3
1 1 1
3
1 2 3
2 3 1
3 1 2
10
1 7 10
3 9 7
2 2 9
5 10 8
4 3 5
7 5 2
6 1 3
9 6 6
8 4 4
10 8 1
1
3
7

Please log in to submit a solution to this problem

Log in