Problem G
Battle of Pokenom

In order to become the very best Pokenom trainer, Bash - the Pokenom trainer - must first understand the Pokenom battle rules.

A Pokenom battle between two Pokenom trainers $A$ and $B$ goes as follow: First, each Pokenom trainer must choose one Pokenom. For simplicity, let’s assume trainer $A$ chooses Pokenom $a$ and trainer $B$ chooses Pokenom $b$. The battle consists of exactly $K$ rounds. In each round, there are exactly two steps:

• Step $1$: Pokenom $a$ attacks Pokenom $b$. The attack can be effective or not effective.

• Step $2$: Pokenom $b$ attacks Pokenom $a$. The attack can be effective or not effective.

If an attack is effective, the corresponding trainer will receive exactly $1$ point. Otherwise, the trainer does not receive any points. After all $K$ rounds, the trainer with more points wins. If the trainers have the same number of points, the battle is a draw.

Bash watched several Pokenom battles between trainers $A$ and $B$. Bash wrote down the result of all steps (there are exactly $2 \cdot K$ steps in total).

After carefully reviewing the result, Bash noticed something extraordinary: It is possible to know the outcome of the battle before the last step! More formally, for each battle, there exist a smallest step $S \le 2 \cdot K$, such that no matter what happens from step $S + 1$ to step $2 \cdot K$, we know for sure which trainer wins the battle, or if the battle is a draw.

For example, consider the following battle with $K = 5$: (E for ‘effective’ and N for ‘not effective’):

• Round $1$: ‘E E’

• Round $2$: ‘E N’

• Round $3$: ‘E E’

• Round $4$: ‘E E’

• Round $5$: ‘E N’

After $S = 9$ steps (i.e. after the first step of the $5$-th round), $A$ has $P_ A = 5$ points and $B$ has $P_ B = 3$ points. No matter what happens in the $10$-th step, we know for sure that $A$ wins.

Excited, Bash immediately tells his friend Cee $3$ numbers: $S$ - the earliest step after which Bash know for sure which Pokenom trainer wins the battle, $P_ A$ - how many points Pokenom trainer $A$ has after $S$ steps, and $P_ B$ - how many points Pokenom trainer $B$ has after $S$ steps.

After that, Bash tells Cee the result of each step from $1$ to $S$. However, after only $C$ steps, Cee stops Bash and tell him: ‘now I know the result of all steps from $C + 1$ to $S$’.

For example, in the above battle, Bash tells Cee $S = 9$, $P_ A = 5$ and $P_ B = 3$. Bash then tells Cee the result of each step. After $C = 4$ steps, here are the result given to Cee (‘?’ indicates that the result is not given):

• Round 1: ‘E E’

• Round 2: ‘E N’

• Round 3: ‘? ?’

• Round 4: ‘? ?’

• Round 5: ‘? ?’

Because Cee also knows that after $S = 9$ steps, $A$ has $P_ A = 5$ points and $P_ B = 3$ points, he can deduce that $A$ gains $3$ more points in step $5$, $7$ and $9$, and $B$ gains $2$ more points in step $6$, $8$.

As Cee is very smart, he always tells Bash as soon as he can infer the result of all step from $1$ to $S$. In other words, $C$ should be as small as possible. Also, remember that Cee knows the meaning of the number $S$: the winner (if any) is surely determined after $S$ steps, but not after $S - 1$ steps.

Given the result of all $2 \cdot K$ steps, find the numbers $S$ and $C$.

Input

The first line of input contains exactly one positive integer $T$ - the number of test cases $(1 \le T \le 65)$.

$T$ test cases follow, each test case consists of:

• The first line contains exactly one positive integer $K$ $(1 \le K \le 6)$.

• In the next $K$ lines, the $i$-th line contains $2$ space-separated characters, representing the result of the $2$ steps in the $i$-th round.

Output

For each test case, print exactly one line containing $2$ integers $S$ and $C$.

2
5
E E
E N
E E
E E
E N
3
N E
N E
E N

9 4 
4 0