Football Team (Large)

A football team lines up in rows for a photograph. The position of each player is given by two integers $x$ and $y$. Here $y$ is the number of the row the player stands in, and $x$ is the distance from the left edge of that row to the player. All $x$ values are different.

To make the photograph more interesting, players who stand near each other wear shirts of different colors. The rule is the following. For each player $P$:

• If the same row holds a closest player to the right of $P$, that player must have a different shirt color.
• If the previous row, meaning row $y-1$, holds a closest player to the right of $P$, that player must have a different shirt color.
• If the next row, meaning row $y+1$, holds a closest player to the right of $P$, that player must have a different shirt color.

More formally, if there is a player at $(x_1, y_1)$ and a player at $(x_2, y_2)$ with $x_1 < x_2$, the two players must have different shirt colors when both of these hold:

• $y_1 - 1 \le y_2 \le y_1 + 1$
• no $x_3$ satisfies $x_1 < x_3 < x_2$ with a player standing at $(x_3, y_2)$

Find the minimum number of distinct shirt colors that makes this possible.

The first line contains one integer $T$, the number of test cases. Each test case starts with a line holding one integer $N$, the number of players, followed by $N$ lines that each give the position of one player in this format.

x y

Limits

• $1 \le T \le 100$
• $1 \le x \le 1000$
• All $x$ values are different.
• $1 \le y \le 30$
• $1 \le N \le 1000$

For each test case, print one line in this format.

Case #X: c

$X$ is the test case number, starting from 1, and $c$ is the minimum number of colors required.