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$.
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.
For each test case, print exactly one line containing $2$ integers $S$ and $C$.
Sample Input 1 | Sample Output 1 |
---|---|
2 5 E E E N E E E E E N 3 N E N E E N |
9 4 4 0 |