Painting a Fence (Large)

You need to hire painters for a fence. The fence has 10000 contiguous sections, numbered 1 to 10000.

Painters send you offers. One offer is a proposal to paint a contiguous block of sections in a single color. Accept a set of offers so that both of these hold:

• Every section of the fence is painted.
• At most 3 colors are used to paint the fence.

If both can hold, find the minimum number of offers you have to accept. Only the colors of the accepted offers count. Accepted offers may paint overlapping sections.

• One line with an integer $T$, the number of test cases.

Each test case is given as follows.

• One line with an integer $N$, the number of offers.
• $N$ lines, one per offer, each in the format C A B. $C$ is the color, an uppercase string of at most 10 letters. $A$ is the first section and $B$ is the last section the painter would paint, with $1 \le A \le B \le 10000$.

Limits

• $1 \le T \le 50$
• $1 \le N \le 300$

For each test case print one line, in input order, holding Case #X: Y, where $X$ is the case number and $Y$ is the minimum number of offers you have to accept. If there is no acceptable set of offers, print Case #X: IMPOSSIBLE.

In the first test case of the example input, accepting both offers paints the whole fence, 5000 sections each, with no overlap.

In the second case the painters overlap, which is acceptable.

In the third case accepting all four offers would cover the whole fence, but it would use 4 different colors, so that set is not acceptable.

In the fourth case section 4001 cannot be painted.

In the fifth case the first and second offers alone paint the whole fence.