2. Elity filmového plátna

V krajine Absurdistan prekvitá filmový priemysel. A ako sa patrí, každý rok sa koná veľká slávnostná ceremónia, kde sa zídu všetci herci z krajiny a tí najlepší dostanú ceny. Ceny sa udeľujú z absurdného množstva kategórii ako “najžiarivejší úsmev”, “najtragickejší monológ” alebo “najdivokejší výkrik”. Môže to dopadnúť všelijako. Už sa doteraz párkrát stalo, že kategórii bolo viac ako hercov a každému hercovi sa ušla aspoň jedna cena, ale raz aj že jediná ultra-populárna herečka vyhrala úplne všetky kategórie.

Ceremónia prebieha tak, že zaradom v každej kategórii moderátor prečíta meno víťazného herca, potrasie mu rukou, odovzdá mu zlatú sošku a všetci zatlieskajú. Moderátor samozrejme tiež musí byť nejaký herec, lebo diváci majú radi keď je to známa tvár a nie nejaký neznámy človek zo zákulisia. Každá kategória má práve jedného moderátora a jedného víťaza. Medzi kategóriami sa moderátori môžu striedať.

Úloha

Ste členmi organizačného výboru tohtoročnej ceremónie. Zoznam a poradie kategórii už je pevne daný a porota už vybrala všetkých víťazov. Vašou úlohou je už len naplánovať, kto bude kedy robiť moderátora. Na to máte dve dôležité podmienky.

1. V žiadnej kategórii nesmie byť moderátor a víťaz ten istý človek. Nevyzeralo by dobre, keby odovzdával sošku sám sebe, diváci by si mysleli že je to nejaký podvod. Ktorýkoľvek iný herec môže kategóriu moderovať, len nie víťaz.

2. Je lepšie aby sa moderátori nestriedali príliš často. Lebo vždy keď sa striedajú, ten starý bude strašne dlho rečniť že prichádza nový moderátor, a ten nový moderátor mu bude celú večnosť ďakovať za privítanie. A to dokonca aj keby ten nový už niečo predtým moderoval. Čas sú peniaze a divákov to hrozne nudí, takže sa snažte aby viaceré kategórie za sebou moderoval ten istý herec.

Nemusíte vypísať detaily kto presne bude kedy moderovať, stačí keď vypíšete koľko najmenej striedaní moderátorov musí nastať. Prvú kategóriu môže moderovať ľubovoľný herec (okrem jej víťaza), jeho nastúpenie sa neráta ako striedanie.

Formát vstupu

Na prvom riadku je číslo \(t\) - počet testovacích vstupov (rôznych ceremónii). Každú ceremóniu vyhodnoťte zvlášť.

V rámci každej ceremónie je na prvom riadku číslo \(h\) - počet hercov. Na ďalších \(h\) riadkoch sú mená jednotlivých hercov v nejakom neurčitom poradí. Mená majú maximálne 100 znakov a môžu obsahovať ľubovoľné normálne znaky (viditeľné ASCII a medzery). Žiadni dvaja herci sa nevolajú rovnako.

Na ďalšom riadku je číslo \(k\) - počet kategórii. Na ďalších \(k\) riadkoch sú mená jednotlivých víťazov (v prvej, druhej, …, \(k\)-tej vyhlásenej kategórii). Každé meno víťaza je naozaj niekto z tých \(h\) hercov čo sa zúčastnili tejto ceremónie.

V jednotlivých sadách platia nasledujúce obmedzenia:

Formát výstupu

O každej z \(t\) ceremónii vypíšte jeden riadok s jedným číslom: minimálny počet striedaní moderátorov medzi kategóriami.

Príklad

Input:

3
5
Jozef Mrkva
Marina Inoue
Tatiana Lieskovoorieskova
Karol XVI. Gustav
GEORG
10
Jozef Mrkva
Jozef Mrkva
GEORG
Karol XVI. Gustav
GEORG
Marina Inoue
Karol XVI. Gustav
Marina Inoue
Tatiana Lieskovoorieskova
GEORG
3
Adam
Bozena
Cyril
5
Bozena
Bozena
Bozena
Cyril
Bozena
2
Alica
Bob
7
Alica
Bob
Alica
Bob
Alica
Bob
Alica

Output:

1
0
6

Prvú ceremóniu môže začať Tatiana Lieskovoorieskova, vyhrala však deviatu kategóriu, takže ju potom musí niekto prestriedať. Druhú ceremóniu vie celú bez striedania odmoderovať Adam. V tretej ceremónii sa budú Bob s Alicou medzi každou kategóriou striedať.