Painting a fence (small)

You need to hire people to paint a fence. The fence is 10000 contiguous sections, numbered 1 to 10000.

Painters send you offers. Each offer is to paint one contiguous range of sections in one color. You have to accept a set of the 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 conditions can be satisfied, find the minimum number of offers you must accept.

Two accepted offers may overlap. Two colors are the same color only when their strings are equal.

The first line contains the number of test cases $T$.

Each test case is given as follows.

• The first line contains the number of offers $N$.
• The next $N$ lines each contain one offer in the form C A B. $C$ is the color, an uppercase letter string of length at most 10. $A$ is the first section and $B$ is the last section to be painted, with $1 \le A \le B \le 10000$.

Limits

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

Print one line per test case, in the order the cases are given, in the form Case #X: Y, where $X$ is the case number and $Y$ is the minimum number of offers that must be accepted. If no set of offers satisfies the conditions, print Case #X: IMPOSSIBLE on that line instead.

These are the five test cases of the sample input.

• In the first case, accepting both offers paints the whole fence, 5000 sections each, with no overlap.
• In the second case the painters overlap, which is allowed.
• In the third case, accepting all four offers covers the whole fence but uses 4 colors, so it does not satisfy the conditions.
• In the fourth case, section 4001 cannot be painted.
• In the fifth case, accepting just the first and the second offer paints the whole fence.