판자 색칠하기

CE 디지털 회사는 평평한 판자를 칠하는 자동 페인팅 기계(APM)를 만들었다. 판자는 크기가 제각각이며 서로 겹치지 않고 맞닿은 직사각형들로 빈틈없이 덮여 있고, 각 직사각형에는 미리 정해진 색 하나가 지정되어 있다.

APM에는 색마다 하나씩, 서로 다른 색의 붓이 준비되어 있다. 판자를 칠할 때 기계는 색이 $C$인 붓 하나를 집어 든 다음, 그 붓을 든 채로 지정색이 $C$인 직사각형을 하나 이상 칠한다. 칠하기에는 다음 규칙이 있다.

• 물감이 새어 색이 섞이지 않도록, 어떤 직사각형은 그 바로 위에 맞닿은 모든 직사각형이 이미 칠해진 뒤에만 칠할 수 있다. (그림 1에서 직사각형 $F$는 직사각형 $C$와 $D$가 모두 칠해진 뒤에야 칠할 수 있다.)
• 각 직사각형은 한 번에 통째로 칠해야 하며, 일부만 칠할 수는 없다.

판자 전체를 칠하되 붓을 집어 드는 횟수를 최소로 하는 프로그램을 작성하라. 같은 붓을 여러 번 집어 들면 집어 든 횟수를 모두 센다.

첫째 줄에 테스트 케이스의 수 $M$이 주어진다 ($1 \le M \le 10$).

각 테스트 케이스의 첫째 줄에는 직사각형의 개수 $N$이 주어진다 ($1 \le N \le 15$). 이어지는 $N$개의 줄에는 직사각형 하나가 다섯 개의 정수로 주어진다.

$y_1 \quad x_1 \quad y_2 \quad x_2 \quad c$

여기서 $(y_1, x_1)$은 직사각형의 왼쪽 위 꼭짓점, $(y_2, x_2)$는 오른쪽 아래 꼭짓점이고, $c$는 색 코드이다.

• 색 코드 $c$는 $1 \le c \le 20$인 정수이다.
• 판자의 왼쪽 위 꼭짓점은 항상 $(0, 0)$이다.
• 모든 좌표는 $0$ 이상 $99$ 이하이다.

각 테스트 케이스마다 붓을 집어 드는 최소 횟수를 한 줄에 출력한다.