Painting a Board

The CE Digital company has built an Automatic Painting Machine (APM) that paints a flat board. The board is completely covered by adjacent, non-overlapping rectangles of various sizes, and each rectangle has a single predefined color.

The APM has a set of brushes, one distinct color per brush. To paint the board, the machine repeatedly picks up a single brush of some color $C$ and, while holding it, paints one or more rectangles whose predefined color is $C$. Painting obeys the following rules:

• To keep the paints from leaking and colors from mixing, a rectangle may be painted only after every rectangle immediately above it has already been painted. (In Figure 1, rectangle $F$ can be painted only after rectangles $C$ and $D$ have been painted.)
• Each rectangle must be painted in a single pass; partial painting of a rectangle is not allowed.

Write a program that paints the whole board while minimizing the number of brush pick-ups. If the same brush is picked up more than once, every pick-up is counted.

The first line contains an integer $M$, the number of test cases ($1 \le M \le 10$).

Each test case begins with a line containing an integer $N$, the number of rectangles ($1 \le N \le 15$). The next $N$ lines each describe one rectangle with five integers:

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

where $(y_1, x_1)$ is the upper-left corner and $(y_2, x_2)$ is the lower-right corner of the rectangle, and $c$ is its color code.

• The color code $c$ is an integer with $1 \le c \le 20$.
• The upper-left corner of the board is always $(0, 0)$.
• Every coordinate is in the range $0 \le \text{coordinate} \le 99$.

For each test case, print a single line containing the minimum number of brush pick-ups.