직물 정렬하기

직물은 다음 세 가지 속성으로 표현된다.

• 색상 ($\mathbf{C}$): 영문 알파벳 소문자로 구성되며 직물의 색상을 나타내는 문자열이다.

• 내구도 ($\mathbf{D}$): 직물의 내구도를 나타내는 정수이다.

• 고유 식별자 ($\mathbf{U}$): 직물의 ID을 나타내는 정수이다.

Ada와 Charles는 Kick Start 직물 공장에서 일한다. 이들은 매일 $\mathbf{N}$개의 직물을 받고, 둘 중 한 명이 이를 정렬해야 한다. 이들은 다음 기준을 사용하여 정렬한다.

• Ada는 색상($\mathbf{C}$)을 기준으로 사전 순 오름차순으로 정렬한다.

• Charles는 내구도($\mathbf{D}$)를 기준으로 오름차순으로 정렬한다.

• 값이 같으면 고유 식별자($\mathbf{U}$)를 기준으로 오름차순으로 정렬하여 순서를 정한다.

$\mathbf{N}$개의 직물이 주어질 때, Ada와 Charles 중 누가 정렬하더라도 같은 위치에 놓이는 직물의 수를 구하라.

제한

시간 제한: 20초. 메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. 문자열 $\mathbf{C_i}$의 $1 \le$ 길이는 $\le 10$. 문자열 $\mathbf{C_i}$은 영문 알파벳 소문자로만 구성된다. 어떤 두 직물도 $\mathbf{U_i}$이 같지 않다.

테스트 세트 1

$1 \le \mathbf{N} \le 2$. $1 \le \mathbf{D_i} \le 2$. $1 \le \mathbf{U_i} \le 2$.

테스트 세트 2

$1 \le \mathbf{N} \le 10^3$. $1 \le \mathbf{D_i} \le 10^2$. $1 \le \mathbf{U_i} \le 10^3$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 직물의 수를 나타내는 정수 $\mathbf{N}$로 구성된 한 줄로 시작한다. 이어서 $\mathbf{N}$개의 줄이 주어지며, 각 줄에는 문자열 $\mathbf{C_i}$, 정수 $\mathbf{D_i}$, 정수 $\mathbf{U_i}$가 주어진다. 이들은 각각 $i$번째 직물의 색상, 내구도, 고유 식별자이다.

각 테스트 케이스마다 Case #$x$: $y$을 포함하는 한 줄을 출력한다. 여기서 $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 작업자가 색상으로 정렬하든 내구도로 정렬하든 같은 위치에 놓이는 직물의 수이다.

예제 케이스 #1에서 색상으로 정렬했을 때 고유 식별자로 나타낸 직물의 순서는 $1$ 및 $2$이다. 내구도로 정렬했을 때 직물의 순서는 $2$ 및 $1$이다. 따라서 색상 또는 내구도로 정렬했을 때 $0$개의 직물이 같은 위치에 놓인다.

예제 케이스 #2에서 색상으로 정렬했을 때 고유 식별자로 나타낸 직물의 순서는 $1$ 및 $2$이다. 내구도로 정렬했을 때 직물의 순서도 $1$ 및 $2$이다. 따라서 $2$개의 직물이 같은 위치에 놓인다. 두 직물의 내구도가 같으므로 Charles가 이들을 정렬할 때 식별자가 더 작은 직물 $1$이 먼저 오도록 정한다는 점에 유의하라.

예제 케이스 #3에는 직물이 $1$개뿐이므로, 직물을 색상으로 정렬하든 내구도로 정렬하든 위치가 그대로 유지된다.

추가 예제 - 테스트 세트 2

예제 케이스 #1에서는 색상으로 정렬할 때와 내구도로 정렬할 때 둘 다 순서가 같다. 따라서 답은 $5$이다.