Yuki ma ciąg $a$ o długości $n$.

Yuki definiuje operację w następujący sposób:

• Wybierz przedział $[l, r]$ o parzystej długości. Dla każdej liczby całkowitej $i$ takiej, że $l \le i \le r$:
  • Jeśli $i - l$ jest nieparzyste, wartość $a_i$ zmniejsza się o $1$, tzn. $a_i \leftarrow a_i - 1$.
  • Jeśli $i - l$ jest parzyste, wartość $a_i$ zwiększa się o $1$, tzn. $a_i \leftarrow a_i + 1$.

Teraz Yuki chce wykonać pewną liczbę operacji tak, aby wszystkie liczby w ciągu $a$ były równe. Musisz pomóc Yuki znaleźć minimalną liczbę operacji potrzebnych do zrównania wszystkich liczb w ciągu $a$, lub stwierdzić, że jest to niemożliwe.

Wejście

To zadanie zawiera wiele przypadków testowych.

Pierwszy wiersz zawiera dodatnią liczbę całkowitą $t$ ($1 \le t \le 10^5$), oznaczającą liczbę przypadków testowych.

Dla każdego przypadku testowego:

• Pierwszy wiersz zawiera dodatnią liczbę całkowitą $n$ ($1 \le n \le 10^6$).
• Drugi wiersz zawiera $n$ liczb całkowitych $a_1, \dots, a_n$ ($0 \le a_i \le 10^{12}$).

Gwarantuje się, że suma $n$ po wszystkich przypadkach testowych nie przekracza $10^6$.

Wyjście

Dla każdego przypadku testowego wypisz jeden wiersz:

• Jeśli jest to niemożliwe, wypisz $-1$.
• Jeśli jest to możliwe, wypisz liczbę całkowitą oznaczającą minimalną liczbę operacji potrzebnych do zrównania wszystkich liczb w ciągu $a$.

Przykłady

Wejście 1

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

Wyjście 1

1
2
-1

Uwaga

Dla pierwszego przypadku testowego:

• Wykonaj operację na przedziale $[1, 2]$. Ciąg staje się równy $2, 2$, gdzie wszystkie liczby są równe.
• Można udowodnić, że nie istnieje rozwiązanie z mniejszą liczbą operacji, więc odpowiedzią jest $1$.

Dla drugiego przypadku testowego:

• Wykonaj operację na przedziale $[1, 4]$. Ciąg staje się równy $2, 4, 2, 4$.
• Wykonaj operację na przedziale $[1, 4]$. Ciąg staje się równy $3, 3, 3, 3$, gdzie wszystkie liczby są równe.
• Można udowodnić, że nie istnieje rozwiązanie z mniejszą liczbą operacji, więc odpowiedzią jest $2$.

Dla trzeciego przypadku testowego:

• Łatwo udowodnić, że nie da się zrównać wszystkich liczb niezależnie od liczby wykonanych operacji, więc odpowiedzią jest $-1$.