Masala #0734

Xotira 16 MB Vaqt 1000 ms
14

O’chirish o’yini

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!


Kiruvchi ma'lumotlar:

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.


Chiquvchi ma'lumotlar:

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


Misollar
# input.txt output.txt
1
2
3
1 3 2
5
5 3 2 1 4
Saidakbar
Mansurbek