축구팀 단체 사진

축구팀이 사진을 찍기 위해 여러 줄로 늘어선다. 각 선수의 위치는 정수 두 개 $x$와 $y$로 주어진다. $y$는 줄 번호이고, $x$는 그 줄의 왼쪽 끝에서 선수까지의 거리이다. 한 테스트 케이스 안에서 $x$ 값은 모두 다르다.

사진을 더 재미있게 만들려고 가까이 선 선수끼리 셔츠 색을 다르게 하기로 했다. 선수 $P$마다 다음 규칙을 적용한다.

• 같은 줄에서 $P$의 오른쪽에 가장 가까이 있는 선수가 있다면, 그 선수의 셔츠 색은 $P$의 색과 달라야 한다.
• 이전 줄에서 $P$의 오른쪽에 가장 가까이 있는 선수가 있다면, 그 선수의 셔츠 색은 $P$의 색과 달라야 한다.
• 다음 줄에서 $P$의 오른쪽에 가장 가까이 있는 선수가 있다면, 그 선수의 셔츠 색은 $P$의 색과 달라야 한다.

형식적으로 쓰면, $(x_1, y_1)$과 $(x_2, y_2)$에 선수가 있고 $x_1 < x_2$일 때 아래 두 조건이 모두 성립하면 두 선수의 셔츠 색은 서로 달라야 한다.

• $y_1 - 1 \le y_2 \le y_1 + 1$
• $x_1 < x_3 < x_2$이면서 $(x_3, y_2)$에 선수가 있는 $x_3$이 존재하지 않는다

이 규칙을 모두 지킬 수 있는 셔츠 색의 최소 개수를 구하라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스의 첫째 줄에는 선수의 수 $N$이 주어지고, 이어지는 $N$개의 줄에 선수 한 명의 위치가

x y

형식으로 주어진다.

제한

• $1 \le T \le 100$
• $1 \le N \le 100$
• $1 \le x \le 1000$
• $1 \le y \le 15$
• 한 테스트 케이스 안에서 $x$ 값은 모두 다르다.

각 테스트 케이스마다 다음 형식으로 한 줄씩 출력한다.

Case #X: c

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