FMI NO STRESS 13 | XORCards

Cerință

Pentru că se plictiseau într-o zi, Ross și Rachel stăteau la cafeneaua Central Perk și jucau un joc de cărți, numit XOR Cards. XOR Cards se joacă cu un pachet de $2^N$ cărți, pe care sunt scrise numerele naturale de la $0$ la $2^N-1$. Pe rând, Ross și Rachel iau câte o carte din pachet, pe care o pot alege cum vor, și o pun în fața lor, cu fața în sus. Ross ia mereu prima carte. La final, se consideră că unul dintre ei e în poziție câștigătoare dacă are în fața sa o carte $K$ pe care este scris XOR-ul tuturor celor $2^{N-1}$ cărți pe care le are în față, inclusiv $K$.

Dacă exact unul dintre ei e în poziție câștigătoare, câștigă jocul. Altfel, e remiză. Ca să facă jocul mai interesant, prima carte a lui Ross este aleasă de comisie. Considerând că ambii jucători joacă optim, dorim să știm câștigătorul jocului.

Date de intrare

Pe prima linie se găsește $T$, numărul scenariilor de analizat. Pe următoarele $T$ linii apar perechi de forma $N$, $C$, indicând dimensiunea pachetului din al $i$-lea scenariu, respectiv cartea aleasă de comisie pentru Ross în acel scenariu.

Date de ieșire

Fișierul de ieșire va avea $T$ linii. Pe a $i$-a linie se va scrie rezultatul din al $i$-lea scenariu: Victorie dacă ar învinge Ross, Infrangere dacă ar învinge Rachel și Remiza altfel.

Restricții și precizări

• $1 \leq T \leq 200\ 000$;
• $2 \leq N \leq 24$;
• $0 \leq C \leq 2^N-1$;
• Pentru teste în valoare de $10$ puncte, $T \leq 10$ și $N \leq 4$ pentru fiecare scenariu;
• Pentru alte teste în valoare de $30$ de puncte, $T \leq 1\ 000$;
• Pentru alte teste în valoare de alte $60$ de puncte, nu există restricții suplimentare;
• Prin joc optim înțelegem că dacă unul dintre jucători poate forța o victorie, o va forța; dacă nu, dar totuși poate forța o remiză, va forța remiza.

Exemplu

stdin

1
2 3

stdout

Infrangere

Explicație

Prima mutare a lui Rachel va fi să ia cartea $0$. Apoi, indiferent dacă ea rămâne cu cartea $1$ sau $2$ în plus, XOR-ul cărților sale va fi $0 \oplus 1 = 1$ sau $0 \oplus 2 = 2$. În ambele cazuri, Rachel este în poziție câștigătoare, iar Ross va avea $3$ și $2$ ($3 \oplus 2 = 1$) sau $3$ și $1$ ($3 \oplus 1 = 2$), și nu este în poziție câștigătoare în nicunul din cazuri, deci Rachel a învins.