لدى Yuki متتالية $a$ بطول $n$.

تعرّف Yuki عملية كما يلي:

• اختر مجالًا $[l, r]$ ذا طول زوجي. لكل عدد صحيح $i$ يحقق $l \le i \le r$:
  • إذا كان $i - l$ فرديًا، فإن قيمة $a_i$ تنقص بمقدار $1$، أي $a_i \leftarrow a_i - 1$.
  • إذا كان $i - l$ زوجيًا، فإن قيمة $a_i$ تزداد بمقدار $1$، أي $a_i \leftarrow a_i + 1$.

الآن، تريد Yuki إجراء عدد من العمليات بحيث تصبح جميع الأعداد في المتتالية $a$ متساوية. عليك مساعدة Yuki في إيجاد الحد الأدنى لعدد العمليات اللازمة لجعل جميع الأعداد في المتتالية $a$ متساوية، أو الإبلاغ عن استحالة ذلك.

الإدخال

تحتوي هذه المسألة على عدة حالات اختبار.

يحتوي السطر الأول على عدد صحيح موجب $t$ ($1 \le t \le 10^5$)، يمثل عدد حالات الاختبار.

لكل حالة اختبار:

• يحتوي السطر الأول على عدد صحيح موجب $n$ ($1 \le n \le 10^6$).
• يحتوي السطر الثاني على $n$ أعداد صحيحة $a_1, \dots, a_n$ ($0 \le a_i \le 10^{12}$).

من المضمون أن مجموع $n$ عبر جميع حالات الاختبار لا يتجاوز $10^6$.

الإخراج

لكل حالة اختبار، اطبع سطرًا واحدًا:

• إذا كان ذلك مستحيلًا، اطبع $-1$.
• إذا كان ذلك ممكنًا، اطبع عددًا صحيحًا يمثل الحد الأدنى لعدد العمليات لجعل جميع الأعداد في المتتالية $a$ متساوية.

أمثلة

الإدخال 1

3
2
1 3
4
1 5 1 5
5
1 3 1 3 1

الإخراج 1

1
2
-1

ملاحظة

بالنسبة لحالة الاختبار الأولى:

• نفّذ العملية على المجال $[1, 2]$. تصبح المتتالية $2, 2$، حيث جميع الأعداد متساوية.
• يمكن إثبات عدم وجود حل بعدد أقل من العمليات، لذا فإن الإجابة هي $1$.

بالنسبة لحالة الاختبار الثانية:

• نفّذ العملية على المجال $[1, 4]$. تصبح المتتالية $2, 4, 2, 4$.
• نفّذ العملية على المجال $[1, 4]$. تصبح المتتالية $3, 3, 3, 3$، حيث جميع الأعداد متساوية.
• يمكن إثبات عدم وجود حل بعدد أقل من العمليات، لذا فإن الإجابة هي $2$.

بالنسبة لحالة الاختبار الثالثة:

• من السهل إثبات أنه من المستحيل جعل جميع الأعداد متساوية بغض النظر عن عدد العمليات، لذا فإن الإجابة هي $-1$.