울타리 칠하기 (small)

울타리를 칠할 사람을 고용해야 한다. 울타리는 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 10$

테스트 케이스마다 한 줄씩, 입력에 주어진 순서대로 Case #X: Y 형식으로 출력한다. $X$는 테스트 케이스 번호이고 $Y$는 받아들여야 하는 제안의 최소 개수다. 조건을 만족하는 제안 집합이 없으면 그 줄에 Case #X: IMPOSSIBLE을 출력한다.

예제 입력의 다섯 테스트 케이스를 설명한다.

• 첫 번째 케이스에서는 두 제안을 모두 받아들이면 각각 구획 5000개씩 겹치지 않게 울타리 전체를 칠한다.
• 두 번째 케이스에서는 도장공들의 구간이 겹치지만, 겹치는 것은 허용된다.
• 세 번째 케이스에서는 네 제안을 모두 받아들이면 울타리 전체를 덮지만 색이 4가지가 되므로 조건을 만족하지 못한다.
• 네 번째 케이스에서는 4001번 구획을 칠할 수 없다.
• 다섯 번째 케이스에서는 첫 번째와 두 번째 제안만 받아들여도 울타리 전체가 칠해진다.