Gigel a primit de la părinţii lui o jucărie interesantă, sub forma unei matrici de 3 pe 3, cu 9 butoane. Fiecare buton poate fi alb sau negru şi îşi schimbă culoarea atunci când este apăsat. Din neatenţie, Gigel a scăpat jucăria pe jos, iar aceasta s-a defectat, schimbându-şi comportamentul. Astfel, atunci când un buton este apăsat, nu se schimbă doar propria culoare, ci şi culorile butoanelor existente din vecinătatea acestuia (sus, jos, stânga şi dreapta).

!{width:500px}problema/jucarie?grid.png!

!{width:700px}problema/jucarie?grid.png!

În exemplul de mai sus, Gigel începe cu toate butoanele albe şi apasă pe întâi pe buntonul de pe linia 1, coloana 2. Toate butoanele de pe linia 1 şi butonul de pe linia 2, coloana 2, devin negre. Apoi, Gigel apasă pe butonul de pe linia 1, coloana 3. Butoanele 2 şi 3 de pe linia 1 devin albe, deoarece înainte erau negre, iar butonul de pe linia 2, coloana 3 devine negru.

h2. Date de intrare

Fişierul de intrare $jucarie.in$ ...

Fişierul de intrare $jucarie.in$ conţine pe prima linie numărul de teste $T$. Fiecare test este format din exact 3 linii cu câte 3 caractere fiecare. Caracterele de pe fiecare linie sunt fie $'A'$ (reprezentând un buton alb) fie $'N'$ (reprezentând un buton negru).

h2. Date de ieşire

În fişierul de ieşire $jucarie.out$ ...

În fişierul de ieşire $jucarie.out$ se va tipări câte o linie pentru fiecare test, conţinând numărul minim de apăsări de butoane necesare pentru a obţine configuraţia dată în test, pornind de la toate butoanele albe. Dacă configuraţia dintr-un test nu se poate obţine, se va tipări $-1$.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ T ≤ 100$

h2. Exemplu
table(example). |_. jucarie.in |_. jucarie.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 2
  NNN
  ANA
  AAA
  NAA
  ANN
  AAA
| 1
  2

|

h3. Explicaţie
 
...
 

== include(page="template/taskfooter" task_id="jucarie") ==