3. Troška čokolády

V triede na stoličkách usporiadaných do kruhu sedia deti. Na niečo čakajú. Podľa ich žiarivých očí môžeme vytušiť, že čakajú na niečo dobré. Asi to nebude písomka. Nedočkavo sa mrvia a mnohým sa už zbiehajú sliny. Čakajú na nejaké jedlo? Na nejakú maškrtu? Alebo nebodaj čakajú na najväčšiu maškrtu zo všetkých maškŕt, samotnú čokoládu?

Áno, už onedlho príde do miestnosti pani učiteľka a donesie im čokoládu. Bohužiaľ, čokoláda je len jedna¹ a tak sa budú musieť deti o čokoládu podeliť. Niektorým sa možno ani neujde.

Pomôžte pani učiteľke zistiť, koľko najviac detí sa môže z čokolády najesť.

Úloha

Tabuľka čokolády sa skladá z \(r\) riadkov a \(s\) stĺpcov kociek čokolády. Pani učiteľka začne tým, že podá čokoládu niektorému dieťaťu v kruhu. Dieťa si odlomí buď jeden riadok alebo jeden stĺpec čokolády a zvyšok podá dieťaťu, ktoré sedí napravo od neho.

Chlapci sú pažraví a vždy, keď dostanú čokoládu, tak si odlomia čo najväčší kus. Čiže keď má čokoláda viac riadkov ako stĺpcov, odlomia si jeden stĺpec, inak si odlomia jeden riadok.

Dievčatá nie sú až také pažravé a navyše si chcú udržať štíhlu líniu. Odlomia si preto čo najmenší kus, tiež jeden riadok alebo jeden stĺpec, ale vyberú si to, čo má menej kociek čokolády.

Zistite, koľko najviac deťom sa ujde čokoláda, ak pani učiteľka čo najlepšie vyberie, ktoré dieťa začne. Dieťa sa započíta len raz, aj keby sa mu čokoláda ušla viackrát.

Formát vstupu

Na prvom riadku je počet tried \(t\), v ktorých treba vyriešiť tento problém. Na každom z ďalších \(t\) riadkov je popis jednej triedy pozostávajúci z čísel \(r\), \(s\) a reťazca \(Z\).

Čokoláda má rozmery \(r \times s\) kociek. \(Z\) je reťazec pozostávajúci z písmen “C” a “D”, ktorý popisuje, ktoré deti sú chlapci a ktoré dievčatá.

Písmená “C” označujú chlapcov a “D” dievčatá, pričom na prvej pozícii reťazca \(Z\) je dieťa, ktoré sedí najbližšie k tabuli, na druhej pozícii dieťa, ktoré sedí napravo od neho, potom dieťa, ktoré sedí napravo od druhého, a tak ďalej. Prvé dieťa v reťazci zároveň sedí napravo od posledného dieťaťa.

Obmedzenia na veľkosti vstupov sú naslednovné:

Počet riadkov aj počet stĺpcov každej čokolády je aspoň \(1\) a najviac \(10^6\). V každej triede je aspoň \(1\) žiak a najviac \(10^6\) žiakov.

Počet tried je najviac \(10^6\) a navyše vo všetkých triedach dokopy je najviac \(10^7\) žiakov. Všetky čokolády dokopy majú najviac \(10^7\) riadkov a najviac \(10^7\) stĺpcov.

V tabuľke si môžete pozrieť horné obmedzenia na počet tried \(t\) a počet žiakov vo jednej triede \(z\) a počet riadkov \(r\) a stĺpcov \(r\) jednej čokolády v jednotlivých sadách vstupov.

Formát výstupu

Na výstup vypíšte \(t\) riadkov, pre každú triedu vypíšte, koľko najviac detí sa môže najesť čokolády, ak si ju budú deliť spôsobom popísaným v zadaní.

Príklad

Input:

5
4 4 DDDDDDD
4 4 CCCCCCCCCCC
10 1 CCCDDD
10 10 CDCD
4 4 DCDCCCD

Output:

7
4
4
4
7

V tretej triede musia najprv jesť dievčatá, lebo chlapec zje celú čokoládu, ktorá ku nemu príde. V štvrtej triede je čokoláda taká veľká, že sa všetci najedia. V piatej triede budú jesť deti v tomto poradí: CCDDCDC. Tým pádom budú rozmery čokolády postupne (4,4), (4,3), (4,2), (3,2), (2,2), (2,1), (1,1), (0,0) a všetci sa najedia.