Masala #0734

Mansurbek va Saidakbar sonlar ustida o’yin o’ynashni yaxshi ko’radi. Bu o’yinlardan biri o’chirish o’yinidir. O’chirish o’yini quyidagicha bo’ladi.

• Doskada 1 dan N gacha bo’lgan sonlarning ixtiyoriy permutatsiyasi yoziladi.
• O’yinni Saidakbar boshlab beradi va har bir o’chirishdan so’ng navbat o’yinchilarning navbati almashadi.
• Navbati kelgan o’yinchi doskadagi qolgan sonlardan ixtiyoriy birini o’chirishi kerak.
• Doskadagi sonlar o’sish tartibida saralangan holga kelib qolsa o’yin tugaydi hamda navbati kelgan o’yinchi yutqazadi.

Ikkala o’yinchi ham optimal o’ynaydi. Siz o’yinda kim g’olib bo’lishini aniqlang!

Kirish faylining dastlabki satrida bitta butun son, \(T (1 \le T \le 100)\) testlar soni kiritiladi.

Keyingi qatordan boshlab har bir test uchun ikkita satr ajratilgan. Bu satrlarning birinchisida \(N\) (doskadagi sonlar soni, \(1 ≤ N ≤ 15\)), ikkinchisida \(1, 2, \dots , N\) ketma-ketlikning ixtiyoriy permutatsiyasi kiritiladi.

Chiqish faylida har bir test uchun alohida qatorda o’yin g’olibini chop eting!