울타리 칠하기 (라지)

울타리를 칠할 사람을 고용해야 한다. 울타리는 1번부터 10000번까지 번호가 붙은 10000개의 연속된 구간으로 이루어져 있다.

도장공들이 견적을 보낸다. 견적 하나는 연속된 구간을 한 가지 색으로 칠하겠다는 제안이다. 다음 두 조건을 모두 만족하도록 견적의 집합을 받아들여야 한다.

• 울타리의 모든 구간이 칠해진다.
• 울타리를 칠하는 데 쓰는 색이 3가지 이하다.

두 조건을 만족시킬 수 있으면 받아들여야 하는 견적의 최소 개수를 구하라. 색은 받아들인 견적의 색만 센다. 받아들인 견적끼리 칠하는 구간이 겹쳐도 된다.

• 첫째 줄에 테스트 케이스의 개수 $T$가 주어진다.

각 테스트 케이스는 다음 형식으로 주어진다.

• 첫째 줄에 견적의 개수 $N$이 주어진다.
• 다음 $N$개의 줄에 견적이 한 줄에 하나씩 C A B 형식으로 주어진다. $C$는 색이고 길이가 10 이하인 대문자 알파벳 문자열이다. $A$는 칠하기 시작하는 구간 번호, $B$는 마지막으로 칠하는 구간 번호이며 $1 \le A \le B \le 10000$이다.

제한

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

각 테스트 케이스마다 입력에 주어진 순서대로 한 줄씩 Case #X: Y를 출력한다. $X$는 테스트 케이스 번호이고 $Y$는 받아들여야 하는 견적의 최소 개수다. 받아들일 수 있는 견적의 집합이 없으면 Case #X: IMPOSSIBLE을 출력한다.

예제 입력의 첫째 테스트 케이스에서는 두 견적을 모두 받아들이면 5000개씩 겹치지 않게 울타리 전체가 칠해진다.

둘째 케이스에서는 도장공들이 칠하는 구간이 겹치지만, 겹쳐도 괜찮다.

셋째 케이스에서는 네 견적을 모두 받아들이면 울타리 전체가 칠해지지만 색이 4가지가 되므로 받아들일 수 없다.

넷째 케이스에서는 4001번 구간을 칠할 수 없다.

다섯째 케이스에서는 첫째와 둘째 견적만 받아들이면 울타리를 전부 칠할 수 있다.