G. Beshtosh o'yini

Qishloq bolalari orasida mashhur bo'lgan Beshtosh o'yinining bir varianti bor: yerga \(n\) ta g'uj-g'uj tosh uyumlari qo'yiladi, \(i\)-uyumda \(a_i\) dona tosh bo'ladi. Ikki o'yinchi — Anvar va Botir — navbat bilan yurish qiladi. Anvar birinchi bo'lib boshlaydi.

Har bir yurishda o'yinchi istalgan bitta uyumni tanlaydi va o'sha uyumdan kamida bitta, istagancha ko'p toshni olib tashlaydi (butun uyumni ham olib tashlash mumkin). Navbatida yura olmagan o'yinchi (ya'ni barcha uyumlar bo'sh bo'lib qolganda yurish kerak bo'lgan o'yinchi) yutqazadi.

Ikkala o'yinchi ham eng aqlli (optimal) tarzda o'ynaydi. Shu holatda kim g'olib chiqadi?

Nega bu qiziq?

Qarasangiz, uyumlar soni va toshlar joylashuvi juda xilma-xil bo'lishi mumkin — lekin g'alaba faqat bitta oddiy amalga bog'liq ekan: barcha \(a_i\) larning XOR (⊕) yig'indisi! Agar bu yig'indi 0 bo'lsa, boshlovchi (Anvar) qancha urinmasin albatta yutqazadi. Aks holda, u albatta g'olib strategiyasini topa oladi. Bu o'yinlar nazariyasining eng mashhur va "sehrli" natijalaridan biri.

Kiruvchi ma'lumotlar

1-qator: \(t\) (\(1 \le t \le 10^4\)) — sinovlar soni.
Har bir sinov uchun:

•   \(n\) (\(1 \le n \le 10^5\)) — tosh uyumlari soni;
•   2-qator: \(n\) ta butun son \(a_1, \dots, a_n\) (\(0 \le a_i \le 10^9\)) — har bir uyumdagi toshlar soni.

Barcha sinovlardagi n larning yig'indisi \(2 \times 10^5\) dan oshmaydi.

Chiquvchi ma'lumotlar

Har bir sinov uchun — kim g'olib bo'lishini chop eting: Anvar yoki Botir.

Misollar

1

2
3
1 2 3
2
3 4

Botir
Anvar

2

1
1
0

Botir

3

1
1
5

Anvar

Izoh

1-test:
- [1,2,3]: \(1\oplus2\oplus3=0\) → boshlovchi (Anvar) yutqazadi → Botir
- [3,4]: \(3\oplus4=7\ne0\) → Anvar \(4\to3\) qiladi, \([3,3]\) hosil bo'ladi, so'ng oyna strategiyasi bilan g'olib chiqadi → Anvar

2-test:
[0] — tosh yo'q, Anvar yura olmaydi, zudlik bilan yutqazadi → Botir

3-test:
[5] — \(5\ne0\), Anvar hammasini bir yurishda oladi, Botirga yurish qolmaydi → Anvar

Qoida: \(\text{XOR} =0\) → boshlovchi yutqazadi; \(\text{XOR} \ne0\) → boshlovchi yutadi.