Pisici Explozive

Cerință

Doi jucători, Jucătorul $1$ și Jucătorul $2$, joacă un joc de cărți. Pe masă se află un pachet de $N$ cărți așezate față în sus, în ordine (ambii jucători văd toate cărțile). Jucătorul $1$ începe primul, iar jucătorii își alternează rândurile.

Pe rândul tău, iei una sau mai multe cărți de la vârful pachetului, respectând următoarele reguli pentru fiecare carte luată:

Atacuri: Când ești atacat (datorești două rânduri), adversarul tău este sărit. Atacurile se cumulează (tip UNO +2): dacă în primul rând forțat iei o carte $A$, ambele rândurile tale se termină imediat, iar adversarul devine atacat (trebuie să joace de două ori consecutiv). Atacul se întoarce la adversar.

Condiția de înfrângere: Jucătorul care este obligat să ia o carte dar nu mai are nicio carte de luat pierde. Aceasta include începutul rândului (trebuie să iei cel puțin o carte) și situația în care ai luat o carte $E$ dar pachetul este deja gol.

Ambii jucători joacă optim. Determinați cine câștigă.

Date de intrare

Prima linie conține numărul întreg $T$ de teste. Urmează $T$ teste, fiecare pe două linii: prima linie conține numărul întreg $N$, iar a doua linie conține $N$ caractere separate prin spații, reprezentând cărțile de la vârf la bază. Fiecare carte este $S$, $E$ sau $A$.

Date de ieșire

Pentru fiecare test, afișați $1$ dacă Jucătorul $1$ câștigă, sau $2$ dacă Jucătorul $2$ câștigă, pe câte o linie separată.

Restricții și precizări

• $1 \leq T \leq 10$
• $1 \leq N \leq 1 \ 000 \ 000$

Subtaskuri și punctaj

Exemplu

stdin

3
3
S A S
3
A A S
1
E

stdout

1
2
2

Explicație

Exemplul 1 ($S \ A \ S$):

Jucătorul $1$ ia primele două cărți: $S$ (poate continua), $A$ (trebuie să se oprească). Cartea $A$ declanșează un atac: Jucătorul $2$ trebuie să joace de două ori, iar Jucătorul $1$ este sărit.

1. Rândul $1$ al Jucătorului $2$: ia $S$. Pachetul devine gol.
2. Jucătorul $1$ este sărit (nu joacă).
3. Rândul $2$ al Jucătorului $2$: pachetul este gol — Jucătorul $2$ nu poate muta și pierde.

Exemplul 2 ($A \ A \ S$):

Jucătorul $1$ ia $A$ — trebuie să se oprească, Jucătorul $2$ este atacat.

1. Rândul $1$ al Jucătorului $2$ (forțat): ia $A$ — atacul se cumulează: ambele rânduri ale lui Jucătorul $2$ se termină imediat, iar Jucătorul $1$ devine atacat. Jucătorul $2$ nu mai joacă rândul al doilea.
2. Rândul $1$ al Jucătorului $1$ (forțat): ia $S$ și se oprește. Rândul forțat se termină. Pachetul devine gol.
3. Rândul $2$ al Jucătorului $1$ (normal): pachetul este gol — Jucătorul $1$ nu poate lua o carte și pierde.

Exemplul 3 ($E$):

Jucătorul $1$ ia $E$ — este obligat să ia încă o carte, dar pachetul este gol. Jucătorul $1$ nu poate lua o carte și pierde.