Masala #0169

Mirzo Ulug’bek kitob olgani kitob do’koniga bordi. Ming afsuski uning hamyonida birorta ham kitobga yetadigan puli yo’q edi. Buni chetdan kuzatib turgan kitobxona xo’jayini Mirzo Ulug’bekning kitobga qiziqishini ko’rganidan so’ng Mirzo Ulug’bekka kitob sovg’a qilish maqsadida unga o’yin o’ynashni taklif qildi, shu o’yinda Mirzo Ulug’bek necha ball yig’sa, shuncha kitobni sovg’a qilishini aytdi. Tabiiyki Mirzo Ulug’bek bunga ko’ndi va diqqat bilan o’yin shartlarini tingladi:

• Mirzo Ulug’bekga nomanfiy butun sonlardan iborat massiv beriladi.
• Mirzo Ulug’bek massivni ketma-ket elementlardan tashkil topgan, bo’sh bo’lmagan shunday 2 massivga ajratishi kerakki chap tomon elementlaridan tashkil topgan massiv elementlari yig’indisi o’ng tomon elementlaridan tashkil topgan massiv elementlari yig’indisiga teng bo’lishi kerak. Agar Mirzo Ulug’bek bu ishni amalga oshira olsa u 1 ball ga ega bo’ladi, aks holda o’yin o’z nihoyasiga yetadi.
• Har bir muvoffaqiyatli turdan so’ng Mirzo Ulug’bek chap yoki o’ng tomon elementlaridan tashkil topgan massivni o’yindan tashqariga uloqtiradi va o’zida qolgan massiv bilan o’yinni davom ettiradi.

Masalan: dastlab Mirzo Ulug’bekda \([1,2,3,6]\) massivi mavjud bo’lsin, u bu massivni \([1,2,3]\), \([6]\) shaklida ikkiga taqsimlashi mumkin(+1 ball), shundan so’ng \([6]\) ni o’yindan chiqarib, o’yinni \([1,2,3]\) bilan davom ettiradi. U bu massivni \([1,2]\), \([3]\) shaklida ikkiga taqsimlashi mumkin(+1 ball), shundan so’ng \([3]\) ni o’yindan chiqarib, o’yinni \([1,2]\) bilan davom ettiradi. U bu massivni ikkiga taqsimlay olmaydi va o’yin nihoyasiga yetib Mirzo Ulug’bek 2 ball ga ega bo’ladi, ya’ni kitob do’konidan ixtiyoriy 2 ta kitobni tekinga olib ketishi mumkin bo’ladi.

Dastlabki satrda bitta butun son, \(T(1 ≤ T ≤ 10)\) testlar soni kiritiladi. Keyingi satrdan boshlab har bir test uchun alohida ikkita satrning birinchi satrida \(N(1 ≤ N ≤ 2^{14})\) – massiv elementlari soni, ikkinchi satrida \(N\) ta \([0, 10^9]\) oralig’idagi butun son, ya’ni, Mirzo Ulug’bekdagi dastlabki massiv elementlari kiritiladi.

Har bir test uchun alohida qatorda bittadan butun son, Mirzo Ulug’bek kitob do’konidan ko’pi bilan nechta kitobni tekinga olib ketishini chop eting.