Football Team Photo

A football team lines up in rows to have a photograph taken. The position of each player is given by two integers $x$ and $y$: $y$ is the row number and $x$ is the distance from the left edge of that row to the player. Within one test case all $x$ values are different.

To make the photo more interesting, players who stand near each other get shirts of different colors. The rule for a player $P$ is this.

• The nearest player to the right of $P$ in the same row, if there is one, must have a shirt color different from $P$.
• The nearest player to the right of $P$ in the previous row, if there is one, must have a shirt color different from $P$.
• The nearest player to the right of $P$ in the next row, if there is one, must have a shirt color different from $P$.

Written formally, if there are players at $(x_1, y_1)$ and $(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$
• There is no $x_3$ with a player at $(x_3, y_2)$ and $x_1 < x_3 < x_2$.

Find the minimum number of distinct shirt colors that makes such an assignment possible.

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

x y

Limits

• $1 \le T \le 100$
• $1 \le N \le 100$
• $1 \le x \le 1000$
• $1 \le y \le 15$
• Within one test case all $x$ values are different.

For each test case, print one line in the form

Case #X: c

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