ดร. Menji เป็นผู้เชี่ยวชาญด้าน AI ตอนนี้เขากำลังฝึกสอน Bot ซึ่งเป็น AGI (Artificial Game Intelligence)
เพื่อสอนให้ Bot รู้จักวิธีเล่นเกม เขาจึงเล่นเกมกับ Bot ทุกวัน วันนี้พวกเขากำลังเล่นเกมต่อไปนี้:
เกมเริ่มต้นด้วยลำดับของจำนวนเต็มไม่ลบ $2n$ จำนวน คือ $a_1, a_2, \cdots, a_{2n}$ และตัวเลข $S$ หนึ่งตัว เริ่มต้นที่ $S = 0$
Menji และ Bot สลับกันเล่นคนละตา โดย Menji เป็นฝ่ายเริ่มก่อน:
- ในตาของ Menji เขาจะเลือกตัวเลข $x$ หนึ่งตัวจากลำดับ กำหนดให้ $S \leftarrow S \oplus x$ และลบ $x$ ออกจากลำดับ สังเกตว่า $\oplus$ คือฟังก์ชัน XOR (exclusive or) ระดับบิต
- ในตาของ Bot เขาจะเลือกตัวเลข $x$ หนึ่งตัวจากลำดับ และลบ $x$ ออกจากลำดับ
เกมจะจบลงเมื่อไม่มีตัวเลขเหลืออยู่ในลำดับ Menji จะชนะก็ต่อเมื่อ $S = 0$ เมื่อจบเกม มิฉะนั้น Bot จะเป็นฝ่ายชนะ
Menji สงสัยว่าหากผู้เล่นทั้งสองฝ่ายเล่นอย่างเหมาะสมที่สุด ใครจะเป็นผู้ชนะในเกมนี้
ข้อมูลนำเข้า
ข้อมูลนำเข้าประกอบด้วยหลายชุดทดสอบ บรรทัดแรกประกอบด้วยจำนวนเต็ม $T$ ($1 \le T \le 10^5$) คือจำนวนชุดทดสอบ
สำหรับแต่ละชุดทดสอบ บรรทัดแรกประกอบด้วยจำนวนเต็ม $n$ ($1 \le n \le 10^5$) ตามที่อธิบายไว้ในโจทย์
บรรทัดที่สองประกอบด้วยจำนวนเต็ม $2n$ จำนวน $a_1, a_2, \cdots, a_{2n}$ ($0 \le a_i < 2^{30}$) แทนจำนวนเต็มในเกม
รับประกันว่าผลรวมของ $n$ ในทุกชุดทดสอบจะไม่เกิน $2 \times 10^5$
ข้อมูลส่งออก
สำหรับแต่ละชุดทดสอบ หาก Menji สามารถชนะเกมได้ ให้พิมพ์ Menji ในหนึ่งบรรทัด มิฉะนั้นให้พิมพ์ Bot ในหนึ่งบรรทัด
ตัวอย่าง
5
2
1 1 3 3
2
1 1 1 3
3
1 1 4 5 1 4
3
1 9 1 9 8 10
6
1 1 4 5 1 4 1 9 1 9 8 10
Bot
Menji
Menji
Menji
Bot
หมายเหตุ
สำหรับชุดทดสอบแรก ไม่ว่า Menji จะเลือกตัวเลขใด Bot สามารถเลือกตัวเลขเดียวกันได้เสมอ ดังนั้น Menji จึงต้องเลือกเลข $1$ หนึ่งตัวและเลข $3$ หนึ่งตัวเสมอ ทำให้ $S = 1 \oplus 3 = 2 \neq 0$ ดังนั้น Bot จึงสามารถชนะได้เสมอ
สำหรับชุดทดสอบที่สอง Menji สามารถเลือกเลข $1$ ในตาแรกได้ ไม่ว่า Bot จะเลือกอะไร Menji ก็สามารถเลือกเลข $1$ อีกตัวหนึ่งได้เสมอ ดังนั้น Menji จึงได้รับเลข $1$ สองตัวเสมอ ทำให้ $S = 1 \oplus 1 = 0$ ดังนั้น Menji จึงสามารถชนะได้เสมอ