축구팀

한 축구팀이 사진을 찍기 위해 여러 줄로 서려고 한다. 각 선수의 위치는 두 정수 x와 y로 주어지며, y는 줄의 번호를 나타내고 x는 해당 줄의 왼쪽 끝에서 선수까지의 거리를 나타낸다. 모든 x 값은 서로 다르다.

사진을 더 흥미롭게 만들기 위해, 서로 가까이 있는 선수들이 서로 다른 색의 셔츠를 입도록 해야 한다. 이를 위해 다음 규칙을 정한다: 각 선수 P에 대해:

• 같은 줄에서 P의 오른쪽에 가장 가까운 선수가 존재한다면, 그 선수는 서로 다른 색의 셔츠를 입어야 한다.

• 이전 줄에서 P의 오른쪽에 가장 가까운 선수가 존재한다면, 그 선수는 서로 다른 색의 셔츠를 입어야 한다.

• 다음 줄에서 P의 오른쪽에 가장 가까운 선수가 존재한다면, 그 선수는 서로 다른 색의 셔츠를 입어야 한다.

더 형식적으로, (x1,y1)와 (x2,y2)에 선수가 있고 x1<x2라면, 다음 조건을 만족할 경우 두 선수는 서로 다른 색의 셔츠를 입어야 한다:

• y1 - 1 ≤ y2 ≤ y1 + 1이며,

• (x3, y2)에 선수가 있고 x1 < x3 < x2를 만족하는 x3가 존재하지 않는다.

이를 가능하게 하는 데 필요한 서로 다른 셔츠 색의 최소 개수를 구한다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1 GB. 1 ≤ T ≤ 100 1 ≤ x ≤ 1000 모든 x 값은 서로 다르다.

작은 데이터 세트

1 ≤ y ≤ 15 1 ≤ N ≤ 100

큰 데이터 세트

1 ≤ y ≤ 30 1 ≤ N ≤ 1000

입력의 첫 줄에는 테스트 케이스의 수를 나타내는 하나의 정수 T가 주어진다. 각 테스트 케이스는 선수의 수를 나타내는 정수 N이 포함된 줄로 시작하며, 이어서 다음 형식의 N개 줄이 주어진다.

x y

각 줄은 한 선수의 위치를 나타낸다.

각 테스트 케이스마다 다음을 출력한다.

Case #X: c

여기서 X는 1부터 시작하는 테스트 케이스 번호이고, c는 필요한 색의 최소 개수이다.