Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AL_05_10 - Gra w wieże

Antek i Basia są rodzeństwem, a ich ulubioną zabawą były zawsze klocki. Dzieci są bardzo inteligentne i zwykłe układanie klocków już je nudzi. Postanowiły więc wykorzystać je w jakiś nietypowy, ciekawszy sposób i wymyśliły niedawno grę opartą na opisanych niżej zasadach.

Najpierw trzeba przygotować dużo (jednakowych, co do wymiarów) klocków w dwóch wybranych kolorach. Weźmy dla przykładu czerwone i zielone. Czerwonych klocków może być nieco więcej niż zielonych, ale nie odwrotnie. Należy jeszcze tylko ustawić z tych klocków dwie jednokolorowe wieże i już można przystąpić do gry.

Dzieci wykonują ruchy na zmianę, a zaczyna zawsze Basia. Każdy gracz w swojej kolejce musi wykonać jeden z trzech ruchów, polegających na zabraniu pewnej niezerowej liczby klocków z jednej lub obu wież.

Dozwolone rodzaje ruchów:

  1. Zabieramy tylko klocki z czerwonej wieży.
  2. Zabieramy klocki z obu wież, ale tyle samo z czerwonej co z zielonej.
  3. Zabieramy klocki z obu wież, ale z czerwonej dwa razy więcej niż z zielonej.

Dodatkowo należy przestrzegać warunku: 
Po żadnym ruchu czerwona wieża nie może stać się niższa od zielonej!

Wygrywa ten, kto zabiera ostatni klocek. 

Basia i Antek doszli już w tej grze do perfekcji (grają optymalnie), więc postanowili ją sobie nieco utrudnić. Budują teraz pewną liczbę par wież i zanim wykonają jeden z opisanych wyżej ruchów muszą najpierw zdecydować, której pary będzie on dotyczyć (dla jasności: pary są ustalone na całą grę i nie można do ruchu wybrać dwóch wież z różnych par). Grają więc teraz na wielu parach wież jednocześnie. Nadal jednak pierwszy ruch wykonuje zawsze Basia i wygrywa oczywiście ten, po czyim ruchu nie będzie już żadnego klocka w grze. 

Okazało się, że przy optymalnej grze każdego z dzieci (a taką trzeba założyć), to kto wygra, zależy tylko i wyłącznie od początkowego stanu wież. Można więc napisać program, który na podstawie liczby wież i ich wysokości, wyznaczy zwycięzcę. To Twoje zadanie.

 

Wejście

W pierwszej linii liczba przypadków testowych (czyli osobnych gier) t (0 < t ≤ 1000).
Każdy test rozpoczyna się linią, w której znajduje się jedna liczba całkowita n (0 < n ≤ 1000) oznaczająca ile par wież mamy w grze.
W każdej z kolejnych n linii, po dwie liczby całkowite c i z (0 < c, z ≤ 1018; 0cz < 45) oznaczające z ilu klocków składają się (odpowiednio czerwona i zielona) wieże w danej parze.

Wyjście

Dla każdego przypadku testowego, w osobnej linii imię dziecka, które wygra.

Przykład

Wejście:
5
1
2 1
1
3 1
2
4 3
4 3
3
5 2
4 4
7 6
4
8 5
3 2
8 3
11 7 Wyjście: Basia
Antek
Antek
Basia
Antek 

Dodane przez:Witold Długosz
Data dodania:2013-04-03
Limit czasu wykonania programu:0.899s-1.200s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU
Pochodzenie:ALGOLIGA
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.