ל-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$.