KTX 열차 기지

KTX(Korea Train eXpress)는 KORAIL이 운영하는 대한민국의 고속철도로, 서울과 주요 도시를 잇는다. 고양차량사업소는 국내에서 가장 큰 차량기지로 KTX 열차의 입출고와 검수를 담당한다.

이 기지의 모든 열차는 자정 전에 기지로 들어와 대기하다가 아침에 다시 떠난다. 각 열차는 기지의 동쪽 끝(E) 또는 서쪽 끝(W)으로 들어오고, 나갈 때도 동쪽 끝이나 서쪽 끝을 이용한다. 열차마다 들어오는 시각과 방향, 나가는 시각과 방향이 미리 정해져 있다.

한 열차는 [t1 d1, t2 d2] 형태로 나타낸다. 이는 시각 $t_1$에 방향 $d_1$으로 기지에 들어와, 시각 $t_2$에 방향 $d_2$으로 기지를 나가는 열차를 뜻한다. 예를 들어 [-6E, 13W]는 시각 $-6$에 동쪽으로 들어와 시각 $13$에 서쪽으로 나가는 열차이다. 그 사이 시간 동안 열차는 어느 선로 위에서 대기한다.

각 선로는 열차를 일렬로 세워 두는 매우 긴 직선 선로이며, 오직 동쪽 끝과 서쪽 끝으로만 열차가 드나든다. 따라서 한 선로에서 어떤 열차가 서쪽으로 나가려면 그 순간 같은 선로에서 가장 서쪽에 있어야 하고, 동쪽으로 나가려면 가장 동쪽에 있어야 한다. 나가려는 방향 쪽에 다른 열차가 남아 있으면 그 열차에 막혀 정시에 나갈 수 없다. 들어올 때도 열차는 자신이 들어오는 방향의 끝에 붙어 자리 잡는다.

예를 들어 열차 [-2E, 2W]와 열차 [-1W, 4W]를 같은 선로에 둔다고 하자. 먼저 [-2E, 2W]가 동쪽으로 들어오고, 이어서 [-1W, 4W]가 서쪽으로 들어와 더 서쪽에 자리 잡는다. 그러면 시각 $2$에 서쪽으로 나가야 하는 [-2E, 2W]가 서쪽에 있는 [-1W, 4W]에 막혀 나갈 수 없으므로, 이 배치는 불가능하다. 두 열차를 서로 다른 선로에 두면 문제가 없다.

또한 서로 다른 두 열차가 같은 시각에 같은 방향으로 동시에 들어오거나 나가는 일은 없다. 선로의 길이는 모든 열차를 세워 둘 수 있을 만큼 충분히 길다.

KORAIL 연구소장은 고양차량사업소에 더 많은 열차를 보관하려 한다. 모든 열차가 다른 열차에 막히지 않고 정해진 시각에 정확히 들어오고 나갈 수 있도록 하려면 최소 몇 개의 선로가 필요한지 구하는 프로그램을 작성하라.

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

각 테스트 케이스의 첫째 줄에는 열차의 수 $n$ ($1 \le n \le 10000$)이 주어진다. 이어지는 $n$개의 줄에는 열차 하나를 나타내는 문자열이 t1 d1 t2 d2 순서로 공백 없이 이어져 주어진다(예: -6E13W). $t_1$과 $t_2$는 정수이고 $-10^6 \le t_1 < 0 < t_2 \le 10^6$이며, $d_1, d_2 \in \{E, W\}$이다.

한 테스트 케이스 안에서 $(t_1, d_1)$이 같은 두 열차는 없고, $(t_2, d_2)$가 같은 두 열차도 없다.

각 테스트 케이스마다 필요한 선로 개수의 최솟값을 한 줄에 출력한다.