PIIMA

Xotira 32 MB Vaqt 1000 ms

14

Uzinliklar soni

Berilgan N butun soni uchun quyidagi shartlarni qanoatlantiradigan sonlar ketma-ketliklarining uzunliklari sonini toping:

Ketma-ketlikdagi barcha sonlarning yig‘indisi N-ga teng bo‘lishi kerak.
Ketma-ketlikdagi sonlar faqat ikkita turdagi qo‘shni butun sonlardan iborat bo‘lishi kerak
Ketma-ketlikdagi sonlari istalgan tartibda joylashishi mumkin.
Ketma-ketlik uzunligi har xil bo‘lishi kerak (faqat har xil uzunliklar hisobga olinadi).

Kiruvchi ma'lumotlar:

Birinchi qatorda T testlar soni beriladi. \((1≤T≤10^4)\)

Keyingi T ta qatorda N ketma-ketlik sonlarining yig‘indisi beriladi. \((1 ≤ N ≤ 10^9)\)

Chiquvchi ma'lumotlar:

Ketma-ketliklarning har xil uzunliklari sonini aniqlang va bitta butun sonni alohida qatorlarda chop eting.

Misollar

#	input.txt	output.txt
1	2 8 12	4 6

Izoh:

1-testda N=8 bo'lsa:

[3,3,2] uzunligi 3,

[1,2,2,2,1] uzunligi 5,

[1,2,1,2,1,1] uzunligi 6,

[1,1,2,1,1,1,1] uzunligi 7.
Jami uzunligi har xil bo'lgan 4 ta hol mavjud ekan.