#213571. [GCJ 2009 #3] Football Team

A football team will be standing in rows to have a photograph taken. The location of each player will be given by two integers and , where gives the number of the row, and gives the distance of the player from the left edge of the row. The values will be all different.

In order to make the photo more interesting, you're going to make sure players who are near each other have shirts of different colors. To do this, you set the following rule:

For each player :

• The closest player to the right of in the same row, if there is such a player, must have a different shirt color.
• The closest player to the right of in the previous row, if there is such a player, must have a different shirt color.
• The closest player to the right of in the next row, if there is such a player, must have a different shirt color.

More formally, if there is a player at and , where , then those two players must have different shirt colors if:

• , and
• there is no such that there is a player at and .

Find the minimum number of distinct shirt colors required so that this is possible.

The first line of input contains a single integer , the number of test cases. Each test case starts with a line that contains an integer , the number of players, followed by lines of the form

each specifying the position of one player.

For each test case, output

Case #X:

where is the test case number, starting from 1, and is the minimum number of colors required.

样例输入 1

3
3
10 10
8 15
12 7
5
1 1
2 1
3 1
4 1
5 1
3
1 1
2 2
3 1

样例输出 1

Case #1: 1
Case #2: 2
Case #3: 3

Limits

• The values of will all be different.

Small dataset(8 Pts)

Large dataset(19 Pts)