Wojna

Treść

„Wojna” to obok „kuku” najpopularniejsza dziecięca gra karciana. Jej zasady są bardzo proste. Talię kart dzieli się pomiędzy zawodników. W każdej turze zawodnicy wykładają po jednej karcie. Zwycięża karta najstarsza, przy czym starszeństwo jest tu tradycyjne. W przypadku blotek i dziesiątki decyduje liczba na karcie. W przypadku figur, które są starsze od wszystkich blotek, najstarszą kartą jest as (oznaczony jako A), następnie król (K), dama (Q) i walet (J). Kolor karty nie ma tu znaczenia. Gracz, który wygrał turę zabiera karty i kładzie je na spód swojej puli. Jeżeli zostało wyłożonych kilka kart o największej sile (np. dwa króle i dziewiątka lub trzy walety, dwójka i trójka) rozpętuje się „wojna”. W tym wypadku właściciele najstarszych kart wykładają jeszcze po dwie karty, jedną na zakładkę i drugą na wierzch. Wygrywa ten, którego karta na wierzchu jest najstarsza. Jeżeli nie można wyłonić zwycięzcy wojna trwa nadal, tzn. właściciele najstarszych kart wykładają po dwie, itd.

Całą grę wygrywa zawodnik, który odbierze wszystkie karty przeciwnikom. Każdy, kto kiedykolwiek grał w wojnę wie, że rozgrywka może toczyć się bardzo długo, a jej wynik jest przesądzony już w momencie rozdania. Dlatego też, w celu zaoszczędzenia cennego czasu, napisz program, który dla zadanego początkowego rozkładu kart wyznaczy zwycięzcę.

Przykłady

Pule kart poszczególnych przeciwników przedstawione są jako ciągi liczb i liter symbolizujących wielkość kart. Górę puli, a więc miejsce skąd karty są wykładane, reprezentuje lewy koniec ciągu. Dół puli, czyli miejsce gdzie dokładane są wygrane przez gracza karty, reprezentowany jest przez prawy koniec ciągu. W przypadku dokładania kart na koniec, w pierwszej kolejności dokłada się karty wyłożone przez gracza 1, następnie karty gracza 2, itd.

Przykład 1

przed turą:
gracz 1: A Q J
gracz 2: 8 K 9
gracz 3: Q J 10

po turze:
gracz 1: Q J A 8 Q
gracz 2: K 9
gracz 3: J 10

W tym przypadku najstarszą kartą (asem) dysponuje gracz 1 i to on zabiera wszystkie karty. Na koniec jego puli najpierw odkładana jest karta gracza 1 (as), następnie karta gracza 2 (walet) i karta gracza 3 (dama).

Przykład 2

przed turą:
gracz 1: A K K Q Q
gracz 2: A Q J J 9
gracz 3: K 9 9 J 8

po turze:
gracz 1: Q Q A K K A Q J K
gracz 2: J 9
gracz 3: 9 9 J 8

Tutaj gracze 1 i 2 toczą ze sobą wojnę. Gracz 1 na zakładkę kładzie króla a na wierzch również króla. Gracz 2 na wierzchu ma waleta i wojnę przegrywa. Wszystkie karty (siedem sztuk) wędrują na koniec puli gracza 1.

Przykład 3

przed turą:
gracz 1: A K 8 8 6
gracz 2: A 3 Q 5 9 K J
gracz 3: A 5 Q 4 7 2 3

po turze:
gracz 1: 8 6
gracz 2: K J A K 8 A 3 Q 5 9 A 5 Q 4 7
gracz 3: 2 3

W tym przykładzie wszyscy trzej gracze wchodzą w stan wojny. Po wyłożeniu kart okazuje się, że najstarsza karta (dama) została wyłożona przez dwóch graczy: 2 i 3. Oni też toczą dalszą walkę, którą ostatecznie wygrywa gracz 2 (kładzie dziewiątkę, która jest starsza od siódemki gracza 3).

Wejście

Dane podawane są na standardowe wejście. W pierwszym wierszu podana jest liczba N (1<=N<=20) zestawów danych. Dalej podawane są zestawy danych zgodnie z poniższym opisem:

Jeden zestaw danych

Pierwszy wiersz zestawu danych zawiera liczbę całkowitą n (2<=n<=8) graczy biorących udział w grze. W kolejnych n wierszach podane są karty kolejnych graczy. Na początku takiego wiersza znajduje się liczba m_i (1<=m_i<=50) kart będących w posiadaniu i-tego gracza. Dalej, po pojedynczej spacji, podane są wartości kart. Wartości te stanowią liczby od 2 do 10 i wielkie litery A, K, Q, J. Kolejne wartości są oddzielone pojedynczymi spacjami. Łączna liczba kart u wszystkich graczy nie przekracza 52 a poszczególne wartości nie występują częściej niż 4 razy.

Wyjście

Wyniki programu powinny być wypisywane na standardowe wyjście. W kolejnych wierszach należy podać odpowiedzi obliczone dla kolejnych zestawów danych. Wynikiem dla jednego zestawu jest numer gracza – zwycięzcy całej rozgrywki. Można założyć, że zwycięzcę zawsze da się wyłonić, a w kolejnych turach nie występuje sytuacja, w której któremukolwiek z graczy nie starczyłoby kart na prowadzenie wojny.

Przykład

dane wejściowe:
2
3
5 A K K Q Q
5 A Q J J 9
5 K 9 9 J 8
3
5 A K 8 8 6
7 A 3 Q 5 9 K J
7 A 5 Q 4 7 2 3

wynik:
1
2