K - Kvadrant 2

Kvadrantovým obrazom rozumieme taký, ktorý, ak to potrebuje, je rozdelený na kvadranty(rovnako veľké štvrtiny : ľavá horná, pravá horná, ľavá dolná, pravá dolná, v tomto poradí)
S rastúcim počtom farieb a kombinácií rastie aj náročnosť na popísanie kvadrantového obrazu, tak sa obmedzíme len na dve farby (označme ich 1 a 2, na obrázku označené červenou a modrou farbou) a výskyt oboch bude daný samostaným jednofarebným obrazom, ktorý budeme nazývať kvadrantovou farebnou maskou .

• R -> Q
• Q -> (QQQQ) | F | V

Maska je buď plne zafarbená - "F", prázdna - "V" alebo čiastočne zafarbená.
V tom prípade sa rozdelí na 4 kvadranty (ozátvorkované, aby bolo jasné, že patria spolu) (v poradí ľavý horný, pravý horný, ľavý dolný, pravý dolný) a pre každý kvadrant sa potom aplikujú tie isté pravidlá.

Platnými reťazcami sú napríklad:

• F
• V
• (FFFF) ( ekvivalentné s F )
• (F(FVFF)(FFVF)F)

Neplatnými reťazcami sú napríklad:

• FF - na nultej úrovni je dovolený len jeden prvok alebo zátvorky
• (FFF) , ((FFVF)) - málo kvadrantov v zátvorke
• (FFFFF) - veľa kvadrantov v zátvorke
• (FF)FVVF(F), (FFVF)) - zle ozátvorkovaný výraz
• (FQVF) neplatný znak, povolené sú len F,V,( a ) (ani medzera)

Hovoríme, že obraz je na úrovni U farby F, ak vo väčšine dielikov úrovne U prevláda farba F:

1. Pre každý dielik úrovne U zistíme, ktorá farba v ňom prevláda
   1. Farba 1
   2. Farba 2
   3. Ani jedna, sú zastúpené rovnako
2. Zistíme počet dielikov, kde prevláda farba 1 a kde farba 2
3. Odpoveďou bude:
   • 1, ak vo väčšine dielikov prevláda farba 1
   • 2, ak vo väčšine dielikov prevláda farba 2
   • 0, inak

Úloha

Pre danú úroveň a kvadrantové farebné masky obrazu zistite, ktorá farba prevláda.

Vstup

V prvom riadku vstupu sa nachádza počet testovacích sád S

Každá sada začína riadkom s celým číslom U

Nasledujúce dva riadky obsahujú textové reťazce R1 a R2 popisujúce kvadrantové masky pre farbu 1 a farbu 2

1 ≤ S ≤ 50
0 ≤ U ≤ 20
1 ≤ |R1|,|R2| ≤ 10 000

Výstup

Výstupom programu je pre každú sadu číslo prevládajúcej farby na úrovni U.
Ak žiadna neprevláda, vypíšte 0.

Príklad

Vstup:

4
2
F
((((FVFV)VFV)FVF)VFV)
3
(FVVF)
(V(FVVV)(VVFV)(FFFV))
1
((FFFV)VFV)
((VVVF)FVF)
2
((FFFV)VFV)
((VVVF)FVF)

Výstup:

1
1
0
2