KTX Train Depot

KTX (Korea Train eXpress) is South Korea's high-speed railway, operated by KORAIL, connecting Seoul with major cities. The Goyang depot is the country's largest rail yard and handles the arrival, departure, and inspection of KTX trains.

Every train at this depot enters before midnight, waits, and leaves in the morning. Each train enters through the depot's east end (E) or west end (W), and it also leaves through the east or west end. For every train, both the arrival time and direction and the departure time and direction are fixed in advance.

A train is written as [t1 d1, t2 d2]: it enters the depot at time $t_1$ from direction $d_1$ and leaves at time $t_2$ toward direction $d_2$. For example, [-6E, 13W] enters from the east at time $-6$ and leaves toward the west at time $13$. In between it waits on one of the tracks.

Each track is a single very long straight siding on which trains stand in a line, and trains can only enter or leave through its east end and its west end. So on a given track, for a train to leave toward the west it must at that moment be the westmost train on that track, and to leave toward the east it must be the eastmost train. If another train still remains on the side it is leaving toward, that train blocks it and it cannot leave on time. When entering, a train likewise parks at the end corresponding to its entry direction.

For example, suppose trains [-2E, 2W] and [-1W, 4W] share one track. First [-2E, 2W] enters from the east, then [-1W, 4W] enters from the west and parks further to the west. Now [-2E, 2W], which must leave toward the west at time $2$, is blocked by [-1W, 4W] sitting to its west, so this arrangement is impossible. Placing the two trains on different tracks resolves the conflict.

Also, no two distinct trains ever enter, or leave, at the same time in the same direction. Each track is long enough to hold every train.

The director of KORAIL's research center wants to store more trains at the Goyang depot. Write a program that finds the minimum number of tracks needed so that every train can enter and leave exactly on time without being blocked by another train.

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

For each test case, the first line contains the number of trains $n$ ($1 \le n \le 10000$). Each of the next $n$ lines contains one train given as the fields t1 d1 t2 d2 concatenated with no spaces (for example, -6E13W). $t_1$ and $t_2$ are integers with $-10^6 \le t_1 < 0 < t_2 \le 10^6$, and $d_1, d_2 \in \{E, W\}$.

Within a single test case, no two trains share the same $(t_1, d_1)$, and no two trains share the same $(t_2, d_2)$.

For each test case, print on its own line the minimum number of tracks required.