Hockey Scores

Time limit1sMemory limit128 MB

Summary

Given unordered score pairs x-y, find the fewest monotone lattice paths from (0,0) that pass through all of them, since each hockey game is such a path.

Level: Medium7 of 10
Topics: Dynamic programming, Greedy, Math, Sorting
Solved: No attempts yet

Problem

Hugh Hockey is a huge hockey fan. Every Saturday night he sits down and watches all of the hockey games, never wanting to miss a moment.

Not this Saturday night, though. Hugh has a date, so he trained his three-year-old brother Billy to record the scores for him. He sat Billy in front of the TV, taught him how to change the channels, and asked him to write down the hockey scores.

When Hugh got home he found a surprise: Billy had written down the scores, but not the names of the teams. Billy had also recorded not only final scores but the scores of games still in progress. Worse, Billy did not follow any consistent order when writing a score, so a score of two-to-one might have been written as 2-1 or as 1-2. There is also no guarantee that Billy wrote down every score; some may have been missed.

In a hockey game the score starts at 0-0 and never goes down: each goal raises one team's total by one. So while a single game is played, both teams' totals only ever increase over time. Since Billy never noted which team was which, a written score x-y matches a moment of a game whenever the two teams have x and y goals at that instant, in either order. One game can account for several of Billy's records.

From Billy's list, help Hugh work out the minimum number of hockey games that could have taken place so that every score Billy wrote down occurs at some moment of some game.

Input

The input consists of several test cases. The first line contains an integer $n$ , the number of test cases.

Each test case begins with a line containing an integer $s$ ( $1 \leq s \leq 1000$ ), the number of scores Billy recorded. Each of the next $s$ lines contains one score in the form x-y, where $x$ and $y$ are non-negative integers.

Output

For each test case, print a single line containing the integer $m$ : the minimum number of hockey games that must have taken place so that every score Billy recorded appears at some moment of some game.

Two records that are equal — including ones written in the opposite order, such as 2-1 and 1-2 — refer to the same score and never force extra games.

Examples6

Example 1

Input

2
4
1-0
2-0
0-3
2-1
4
0-0
5-0
1-3
2-2

Expected output

2
3

Example 2
Input
```
1
1
0-0
```
Expected output
```
1
```
Example 3
Input
```
1
3
2-1
1-2
2-1
```
Expected output
```
1
```
Example 4
Input
```
1
5
0-0
0-1
1-1
1-2
2-2
```
Expected output
```
1
```
Example 5
Input
```
1
5
0-0
0-1
0-2
0-3
0-4
```
Expected output
```
1
```
Example 6
Input
```
3
1
3-3
2
0-5
5-0
3
0-2
2-0
1-1
```
Expected output
```
1
1
2
```